This is a really, really big, complicated question, but I will point out three small things:

1. The specific concept of the "the divine right of kings" aka absolute monarchy, wasn't fully articulated as a coherent political philosohy until the work of Jean Boudin in the mid-1500s. Medieval ideas about kingship were more complex and varied than that. St. Thomas Aquinas argued, for instance, that a ruler who violated natural or divine law was a tyrant and could be justly over thrown.

2. Medieval Christian kingdoms didn't arise out of thin air. They arose out of the Roman Empire. To understand the political development of Europe you need to understand the gradual dissolution of the Western Roman Empire in late Antiquity --- you might try reading Peter Brown's The World of Late Antiquity, it's pretty short and readable. But in a nutshell, the Roman state helped nuture Christianity during its youth, and Christianity ended up the only institution of that state to survive the empire's decline and retain the ability to confer some connection to it --- a seal of legitimacy that remained a valuable prize for centuries and helped place the church at the center of European politics. In other words, the church was a player in the game, not the ref --- sometime winning power, sometimes losing it, sometimes allying with this king, sometimes with another.

3. At the end of the day, who rules a place generally comes down to who's got the money, army, and alliances to control the territory and enforce their will. If one charismatic leader is able to collect and reward enough followers, you might end up with a kingdom (or a dukedom, at least). If a bunch of wealthy aristocrats decided to band together against a common enemy, you might end up with a republic. And if you're not worth the conquering, you might get left alone --- that's how a tiny monestary turns into a tiny city turns into a tiny country turns into the world's oldest republic --- being on top of a very big, barren mountain.