not calling them anything at all
Ah, I see you've found my method of speaking to my future in-laws without it sounding awkward. But yeah, I think this may be the way to go. As
@Banespawn suggested, using the title in limited circumstances as a reminder, but otherwise leaving it out.
Have people call them Larry, Moe, Curly? I jest.
I think any sycophants are going to call them whatever they most prefer to be called since that's most likely to keep their heads attached or whatever. Maybe the prince doesn't like being called Your Highness and instead wants to be called Lord Bob, Bob for short. Maybe the thing he says he wants to be called varies not by the person saying it, but rather by his mood? Honestly the possibilities are endless.
I will say, this now has me thinking of having a different royal who is
super serious about their titles.
"Your Highness-"
"Your Highness? Lord Fauntleroy, I didn't spend six years fending off the southern invasion just to be called Your Highness! I earned all my titles, damn it."
"Apologies, Your H-" he paused. "My King, First of His Name, Lord of the Southlands, Lover of the Birds Both Wingless and Winged, Commander of the First Army, and Protector of the Realm."
It isn't necessary to use the honorific every time an underling speaks to the king/prince. When first called upon, the underling might respond with the honorific. And if the king/prince issues a command, again, the underling might respond with the honorific. Everything in between probably doesn't need it unless it's a lengthy conversation. Treat it similar to dialogue tags when two people are talking. Throw one in every so often just to remind the reader.
Regarding the headsmen, I would drop the title once it has been established. I would also change Headsman Man's name. Byron and Dickory are fine.
I will not tolerate Head Headsman Man slander!
In all seriousness, it's a name that some people absolutely hate, but I've had tons of readers tell me I needed to keep it. It fits the ridiculous tone of my story (for fuck's sake, I have an executioner named Garumund Executionerson, lol).