Имеет ли смысл публиковать Android-игру в сторонних магазинах?
Да, бесплатные игры нужно размещать везде, где возможно. Немного закачек тут, немного там…

И хорошо бы ещё договориться с какими-то локальными издателями. В той же Корее вы сами вряд ли сможете в их магазинах что-то опубликовать, а база пользователей там большая. К тому же, помимо публикации издатель сам пиарить игру будет, так как это в его интересах)
Мой ответ, конечно, необъективен — но я всё же рискну посоветовать Amazon Appstore.
Как минимум, вы получите доступ ко всем устройствам Kindle Fire (сейчас их пока четыре).
Подавляющее большинство их пользователей не имеет доступа к Google Play — соответственно, хороший потенциал для увеличения закачек.
Кроме того, есть немало людей, имеющих его (Amazon Appstore) и на телефоне.

У Appstore есть ещё немало хороших штук, но это уже совсем было бы рекламой.