The surname "King" was often a product of Anglicizing and Americanizing foreign surnames to be more palatable to local ears and tongues, a common practice among immigrants (or officials who dealt with them) in centuries past. One example is the Irish name Conroy, borne by various clans particularly in Connacht; "Mac Conroy" was interpreted as a variant spelling of "Mac an Righ," literally meaning son of the king, and upon the advent of English rule over Ireland was frequently changed to "King" in both personal and place names.

McQueen is likewise an Anglicized Gaelic surname that originally had nothing to do with queens, though there is disagreement concerning which name it originated from (possibly more than one.)

As for the other names, I can find no particularly authoritative source for this, so treat it as conjecture, but many genealogists seem to believe surnames like King and Prince frequently originated as bynames—that is, they were nicknames given to a person who for some reason (personality, etc.) reminded their acquaintances of a king or prince. This is how many an English surname originated, so it seems eminently plausible to me.

Source for the Conroy fact: "A chorographical description of West or H-Iar Connaught: written A.D. 1684" by Roderic O'Flaherty

Something very common in English is the avoidance of learning any new words or names. Thus, when the cultivation of asparagus was introduced to the ordinary English farmer, rather than learn a new word they called it "sparrow grass." In the same way, any old or foreign word may be twisted into something out of their extant vocabulary. An unfamiliar place name, used as a family name, will become a familiar vocabulary word, preferably a noun, resulting in some of the more amusing names of the British Isles.

McQueen is a Scottish name, having nothing to do with the AS "quean/queen." To quote Johnston:

"M'Queen, 'Quine

"M'B. says, 'son of Suibhne,' i.e., 'Goodkin' or Godkin. But this is seen rather in the Ir. M'Sween, M'Sweeny; and there is actually a Hector Mac Souhyn, 1271, in Paisley Chart. The old forms favour G. caoin, -ne, 'kind, pleasant' man.

"[1403, Luke Macquyn, I. of Man.] 1489, Joh. Makquhen, Paisley. 1502, Thom. M'Quhinze, Ayr. A. 1577, Wm. Makquene in Assynt. A. 1595, Rev. Pat. M'Queine, Rothesay. 1596, Mich. M'Qwin, Ayr."

Firstly, most Norman nobles took their surnames, later family names, from their estates, whether the ones they got in England or that they came from in France, not from their titles.

The exception would be the Fitzfulks, Fitzwilliams, &c. This was a simple patronymic, so that Fitzhugh was "son of Hugh." (From Filz, from fils.) This was used as a surname (after-name) before there were inheritable family names, and changed with every generation. It was exactly like an AS thegn being known as Bodda, Brand's son, or a Russian as Nicolai Alexandrovich, or an Icelander as Tosti Eriksson. But Henry II was known as Fitz-Empresse. Camden lists matronymics like Fitz-Isabel and Fitz-Mary. So understand patronymic as meaning either parent.

The first Fitz-Roy was said to be Robert, bastard of Henry I. There were no Fitz-dukes or Fitz-earls. It was a peculiarity of royal bastards. So, no, family names like Duke didn't happen that way.

Edward I didn't like Fitz-names, so that many of his nobility left off using them in favour of estate names (he ordered Sir John Fitz-Robert to become Sir John of Clavering, his primary estate). They didn't just drop the Fitz and become de Robert.

Cornish names are almost entirely place names, based on farms the yeomen worked, with occasional occupational or patronymic names. Welsh names, on the other hand, are almost all patronymics, with the occasional occupational or locale name. All the Irish and Scottish O'- and Mac/Mc/M'- names are patronymics.

Names like Abbot are not likely to be the result of having a clerical ancestor. Rather, the ancestor worked for the abbot, and was Jack o' the abbot. So you wind up with Jack Abbot, the running footman, William Duke, the gardener, and so on.

"King" is almost always the result of an ancestor playing a king in mystery plays, one of the Three Wise Men or King Herod. Once a part was learnt, the player would not often be changed. So Dickon King was the fellow who played the part for ten years. These are sometimes called "pageant names."

As Harrison says,

"PRINCE (A.-Fr-.-Lat.) a nickname (applied e.g. to a prince's servant) and pageant-name [Fr. prince ; Lat. princeps, chief, leader]"

Though the 1602 list of surnames has Duke, King, and Prince, there's no sign of Queen. Between surname time and family name formation, it may have fallen victim to the use of "quean" in various spellings to mean "whore."

SOURCES:

Barber, Henry. British Family Names: Their Origin and Meaning. (1968) Baltimore: Genealogical Publishing Company.

Bardsley, Charles Wareing Endell. A Dictionary of English and Welsh Surnames, with Special American Instances. (1901) London; New York: H. Frowde

Bardsley, Charles Wareing Endell. Our English Surnames: Their Sources and Significations. (1875) London: Chatto and Windus.

Bardsley, Charles Wareing Endell. The Romance of the London Directory (1879)

Baring-Gould, Sabine. Family Names and Their Story (1913) Philadelphia: Lippincott

Camden, William. Remaines of a Greater Worke, Concerning Britaine: their languages, names, surnames, allusions, anagrammes, armories, monies, empreses, apparell, artillarie, wise speeches, proverbs, poesies, epitaphs (1605): London. This Clarenceaux king of arms knew more about the families of England and the mutation of their names and arms than any normal human could.

Daniel, James Walter. A Ramble Among Surnames (1893) Nashville, TN: Publishing House of the M. E. Church, South. Merest guesswork for the most part.

Ewen, Cecil Henry L’Estrange. A History of Surnames of the British Isles: A Concise Account of Their Origin, Evolution, Etymology, and Legal Status. (1931) Baltimore: Genealogical Publishing Company, .

Finlayson, James Surnames & Sirenames. The Origin and History of Certain Family & Historical Names; with remarks on the ancient right of the crown to sanction and veto the assumption of names. And an historical account of the names Buggey and Bugg. (1863) London: Simpkin, Marshall and Co.

Harrison, Henry. Surnames of the United Kingdom: a concise etymological dictionary (1912): who decries Lower as quite obsolete.

Hitching, F. K. & S. References to English Surnames in 1602; An Index Giving About 20,500 References to Surnames Contained in The Printed Registers of 964 English Parishes during The Second Year of the 17th Century. With An Appendix Indexing the Surnames Contained in 186 Printed Registers during 1601 (omitted from the volume for that year) (1911): London: Charles A. Bernau.

Innes, Cosmo. Concerning Some Scotch Surnames (1860) Edinburgh, Edmonston and Douglas.

Johnston, James B. The Scottish Macs: Their Derivation and Origin (1922) Paisley, (UK): A. Gardner. Traces back to first appearances, but almost always spells as M'___.

Long, . Personal and Family Names (1883)

Lower, Mark Antony. A Dictionary of the Family Names of the United Kingdom (1860) aka Patronymica Britannica.

Lower, Mark Antony. English Surnames. An Essay on Family Nomenclature, Historical, Etymological, and Humorous; with Several Illustrative appendices. (1849) London: J. R. Smith

Paterson, James. Scottish Surnames; Contribution to Genealogy. (1866) Edinburgh: J. Stillie

Sims, Clifford Stanley. The Origins and Signification of Scottish Surnames, with a Vocabulary of Christian Names. (1968) Baltimore, Maryland: Genealogical Publishing Company.

Wagner Names: and Their Meaning, a Book for the Curious (1891)

Weekley, Ernest. The Romance of Names. (1914) New York: Benjamin Blom, .

White, G. Pawley. Cornish Family Names. (1972) Cornwall: Dyllansow Truran, .