Not to discourage further discussion, but you may find /u/koredozo's and /u/Zither13's response in this thread to be helpful

Follow up question: for irish and scottish names that begin with C, like Conroy/Connor/Connolly/Connell/Callaghan/Cagney/Coughlin etc - are these all formerly Mc/O names that have been shortened? Or is there a different rule?

For the English language use of the surname King, A Dictionary of English Surnames by Percy Reaney and R.M. Wilson states that "[s]urnames of office, such as Abbot, Bishop, Cardinal and King, are often nicknames". Reaney and Wilson's entry on the surname King thus gives the following explanation:

"a nickname from the possession of kingly qualities or appearance. Also a pageant name, one who had acted as king in a play or pageant, or had been King of Misrule, or 'king' of a tournament."

They give examples of the surname in use going all the way back to 1201, which isn't far after permanent surnames began appearing in England.

One family history book offers a little bit more of an explanation:

"In the Domesday book [which was written in Latin] the smaller proprietors, whose christian names alone were given, were grouped in classes as 'servientes Regis,' 'Taini Regis' or 'Elesmosynarii Regis,' that is the king's serjeants [sic], the king's Thanes, the king's Almsmen, etc. Each tenant of the king being described by his christian name and the land he held. So it could happen that the tenant of a royal estate would, when spoken of as a tenant, be called, for instance, 'Roger, the king's,' and in time the surname of descriptive name would become merely 'King'--Roger King, from the fact he was a tenant of the king."

In other words, the King owned land and had tenants, and when peasants were first being given surnames in the aftermath of the Norman Invasion, some of them were given the surname "King" because that's whose land they lived on. But not every tenant who lived on the King's land would be given this surname, and the "King" might not even refer to the King of England, just the head of a large clan in that area of England.

So the name does have a connection to noblemen/kings, but the people who had the name are thought not to be noblemen themselves, but likely had a direct connection to a nobleman or king. The noblemen themselves would usually get a surname reflecting the name of their title, "William of Essex" and so on.

That family history book also offers up another alternative, similar to what Reaney and Wilson stated: "passion plays" were a part of old European culture, and the parishioner who would play Christ, or the "King", in the annual play was given the surname "King" when permanent surnames were adopted in the area (in England, it generally began to happen sometime between the mid-1100s to mid-1300s, depending on the area, with surnames becoming definitely permanent in the mid-1500s with the introduction of church baptism record-keeping).

But, like with any surname etymology, it can vary from one lineage of the surname to another. As the other replies said, some "King"s were likely anglicized names from other languages, while others have roots in Norman England. You'd have to track down the genealogy of any individual line to know for sure what that line's roots are, but, unfortunately, since some of those lines will predate baptism records in England, you may not be able to connect an unbroken paper trail that dates all the way back to when the surname first appeared. In those cases, there will remain some mystery behind the exact origin of the surname.

Can I ask a follow up? (unless it's a new post kind of thing)

My Surname is Barone - we're originally of Italian origin, so like the title Baron - what's the likely circumstance that an Italian person or family end up with a name like that?

Similarly, what's the story behind the Jewish surname Koenig? Does it suggest descent from the Davidic line?