How does one even become a monarch? They weren't always hereditary, and it would be interesting to see what they were based on. Seems like you need some kind of divine recognition, as otherwise you're just a dictator.
To answer the question of how hereditary monarchies get started: in the modern era (post-Napoleonic Wars, generally), new monarchies carved out of existing states either elevated important local elites (the Sharif of Mecca's sons got kingdoms in Iraq and Transjordan out of WWI, with the Sharif himself proclaiming a kingdom in Hejaz), or they shopped around important royal families in Europe to import a monarch (e.g., a lot of German princes found themselves kings of newly-created Balkan states in the 19th century). The right of conquest to attain a royal title is pretty well-accepted, although conquest usually comes from someone who already has a heritable noble title anyways (cf. the Dukes of Normandy becoming Kings of England).
The older noble lineages in Europe (and elsewhere, but I really don't know much about the history of nobility outside of Europe) appear to largely arise from a Germanic system of elected chiefdoms where one family gradually gains enough power to force the elections to choose them, eventually (though not always, cf. the Holy Roman Empire) dispensing with the pretense of election. Given the paucity of written sources, we obviously have very little record of how these influential families actually came to gain their influence, and the sources that we do have tend to be edited to suggest divine providence as the originator of their rule.
Pretty fascinating history overall. In England's case, the earliest monarch we'd recognize as "King of England" was Alfred the Great, who was king of what was called Wessex at the time. Wessex was the last holdout of "native" English as opposed to being ruled by Vikings and their descendants. Wessex eventually re-conquered the island a few hundred years later and became England.
As to how earlier kings gained their position, at least in England I'd say it was some combination of local warlords that were semi-legitimized during Roman rule, then later their descendents consolidated power after the Romans left, either through marriage, trade, or violence.
That definitely didn't happen. The locals in Roman Britain would be the Bretons, a Celtic-speaking people. The withdrawal of Roman power from Britain was followed with the Anglo-Saxon migrations of people from what is now the Netherlands, Germany, and Denmark, which (actually rather rapidly) displaced the Celtic speakers with Germanic speakers. The Anglo-Saxon petty kingdoms arose after the migration, although they were subsequently occupied by the Great Dane Army that settled in the Danelaw region of England. It was the Mercian (one of the Anglo-Saxon kingdoms) failure to deal with the Vikings and Alfred the Great's success that led the Wessex king, and not the then-dominant Mercian king, to actually unify all of the Anglo-Saxon kingdoms into a single Kingdom of England.
The origination of these Anglo-Saxon kingdoms is extremely unclear, happening during the Great Migration and in an area where the written record rather abruptly dies out. Virtually the entire list of sources for this period is Bede's Ecclesiastical History of the Peoples of Britain and the Anglo-Saxon Chronicle commissioned by Alfred the Great.
A better answer for the UK in line with your point about religious recognition is that you are anointed monarch. There is a coronation ceremony where the heir is anointed with holy oil (chrism) by the Archbishop of Canterbury. After that, they stop being an ordinary person and become monarch.
You can see part of the coronation of Elizabeth II (and hear the incredible Zadok the Priest coronation anthem by Handel) here [0], although not the anointing itself, because it happens under a canopy and has never been filmed.
https://en.m.wikipedia.org/wiki/Order_of_succession
For example that article mentions the Kingdom of Italy was briefly had this as the succession law:
The Kingdom of Italy was designated a secundogeniture for the second surviving son of Napoleon I Bonaparte but, failing such, provided for the emperor's stepson, Eugène de Beauharnais, to succeed, even though the latter had no blood relationship to the House of Bonaparte
Actually, it is true but not exhaustive. Nor was it intended to be. I was addressing the context of monarchy in the UK, as the rest of the comment makes clear.
IIRC, you conquer a territory, descend (biologically or legally) from someone who did, or politically maneuver to replace an existing monarch or heir (for instance, by assassinating them).
I think the options for becoming a monarch are:
1) the birth heir of a current hereditary monarch
2) the designated heir of the current monarch (e.g. some Roman emperors were appointed by their predecessor. Although the August didn't call himself "king" because of the historical political animosity to a king, he did intend for the position to be hereditary, but the first few emperors had trouble having sons. Whether the emperors were monarchs is arguably semantic, although Rome was more of an empire [extracting resources from the periphery] than a feudal state, which would argue that they are not monarchs by my definition above. On the other hand, Roman administration of provinces wasn't as strong as a nation-state.)
3) get elected as monarch [https://en.wikipedia.org/wiki/Elective_monarchy]
4) conqueror somewhere and establish a feudal state. It might be necessary for you to have a successful succession in order for history to call you king, though.
I'd argue you have it backwards there. You start as a dictator (you and a bunch of people who agree with you take over some part of land, congrats you're the King) then the legitimacy comes from you and your family holding on to it till everyone's used to it.
In the Holy See: you have people from several factions argue whose candidate should be Pope, and then you compromise on a Pole (Wojtila).
Just call yourself one, and have enough people agree with you.