By The Grace of God

With regard to the Orthodox Kingdoms, very few of them (only Georgia comes to mind, and Armenia too, but way before the game's starting date) were recognized by Constantinople as such. The others (Serbia, the first and second Bulgarian Kingdoms) gained their independence and recognition generally by force of arms. Hungary is also a case in point as it chose Catholicism precisely because the Pope's offer came with the crown included, while the Eastern Roman Empire hesitated (wishing to offer just another Grand Duke title, akin to Kiev's). So, there should be possible to proclaim yourself as king and defend that title by force of arms (the farther away from the power centres, the easier it should for your dinasty to be reconginzed as such).