I have an old ballad called "Down, Down Derry Down" which tells the story of a farm boy sent to town to sell a cow. He is later accosted by a highwayman who tries to get his money, but thee is a happy ending.
This is very old, but doesn't have any reference to a king. Also, doesn't appear to be your melody.
I thought, "Well, maybe."