Recorded history begins in the late fourth millenium with the invention of writing in Mesopotamia and Egypt. At the time, kings already existed. So "the first king ever" is from far back in prehistory. There are no records from whenever that was, and so it's impossible to know exactly what happened.
In the particular case of the Near East, kings were often considered gods, sons of gods, or became gods after they died. Just one example (from the Sumerian king list):
After the kingship descended from heaven, the kingship was in Eridug. In Eridug, Alulim became king; he ruled for 28800 years.
Of course, a historian would probably consider this account mythological, and not representative of what actually happened.
Other theories (a famous example is that of the social contract) are advanced in philosophy, but are not exactly in the realm of history.
A more practical question is how kingship started in a particular society. For example, if you were interested in how the monarchy started in ancient Israel, you could read about Saul, the first king. If you were interested in how the Roman Kingdom became the Roman Republic and then became the Roman Empire, you could read about how each regime changed. All of these beginnings happened after kings had long existed, and the societies involved in the changes would have been well aware of kings from other nations; there is no documentation for "the first monarch ever."