The early 19th Century song clubs out of which Victorian music-hall grew were pretty low places. Cheap books of bawdy songs were printed for their audiences, books with titles like 'Fanny Hill's Bang-Up Reciter'. An item found in some of these books is a song called 'The Queen of the Cannibal Islands'. The chrus is as much as I will quote here, but is sufficient to show a) that the song is related to the 'King of..' version, and b) the nature of the 'Queen of...'. The chorus runs:

Hokey pokey, wankee fum,
Clap your fingers under my bum,
That's the way to make me come,
Says the Queen of the Cannibal Islands.

The songbooks are about 1820s/'30s, but whether they might contain any evidence as to which came first I don't know.