For most of western Romania, Barbarian kings were alreadt in charge of their peoples trough a legalized warlordism : Barbarian kingship was acknowledged by imperial bureaucracy and both ended up surviving the Roman state and blending together into a post-imperial state. Their kings were legitimized trough this para-legal transition of power, more or less supported by local administration (various Roman local governors, clergy, etc.) and by a remote imperial intervention (imperial insignas being given to Theoderic, Clovis being consul, etc.). Would these kings be regional overlords or quickly submersed petty-kings, their establishments is a legacy of the Late Roman Empire.
The legitimisation of post-imperial Britto-Roman kingship seems to have similarily evolved from the collapse of Roman Britain but in this case trough the mix-up of military and civilian authority as soon as the late IVth century. They were still legal authorities, rather inherited legal authority than proceeding from it.

English kingship, however, took a bit more time building-up from a set of relatively egalitarian and familial communities in the Vth century both from service to Britto-Romans, but as well a slow evolution which favoured ruling families trough clientelism. Legitimisation was made a posteriori in the VIth century, arguing of an "imported" kingship from overseas and royal-divine ancestry.

It's not really clear how Barbarian kingship outside Romania was legitimized, and there's few evidence : their legitimacy might be a mix of royal bloodine and partnership with post-imperial states : for exemple, Thuringians being client of Goths then Franks, enforced trough geneaogic and familial ties.

It's a massive question, because generally historical sources postdates the formation of these kinds of governments: We get kings, who require (in some cases!) writing. (or at least merchants...)

"Who was the first King and how did he come to power?" is one of those hard problems, becuase we don't get any real records until long afterwards, when the process has already passed into legend.

Specifically for the germanic kingdoms, "kings", were generally in soem form already extant: Who they ruled over wasn't neccessarily established, but that, for instance, there was a King of the Franks was. (some historians have pointed to a difference between roman usage, where someone was King of a place, and barbarian usage, where someone was king of a people, but there's been a lot of debate over whether or not that distinction actually holds up)

Generally speaking these kings were members of powerful families, but also required to some extent the acceptance of other powerful families (sometimes "all the warriors", or some similar statement, again, exactly how many people that encompasses is very vague) there are also examples of a people having several kings, or being divided into several groups.

In at least some germanic societies, kingship might have been associated with certain religious functions (there were certain sacrifices that could only be performed by the king) in almost all cases the king was in charge of leading the army. But other than that the king's role and powers varied wildly.

But it is important to note that in late antiquity, kingship already exists in some form: The germanic peoples were already in some sense stratified societies, with a warrior-elite, and a king on top. What happens is that these kingships are redefined (some are destroyed, some are expanded, some merged, sometimes new ones are made up, lots of influence is had from roman ideas of rulership, etc. ) but the kingship as an institution is already there.