Что будет с приложениями купленными в Android Market после перепрошивки телефона?
Перепокупать не придется.

Что с ним случится после перепрошивки — перепрошивка его сотрет, но он останется в вашем аккаунте. При входе в GooglePlay оно будет отображаться как купленное. Его можно снова загрузить.

Приложение можно установать на любое устройство в аккаунте, с которым оно совместимо (в противном случае ругнется).

Не бойтесь покупать — все будет хорошо.
Ничего покупать не надо будет — приложение на аккаунт покупается. 
В случае со сторонними прошивками может возникнуть проблема с тем, что из коробки у них нет Play, но оно решаемо.