We tried the following for the three player variant and it worked fairly well:
At the start of the round, deal 1 down, 2 up, each player chooses a character, and then the final one goes down.
As per other rules if the king is dealt up, he gets reshuffled in, and another character is picked.
It seems slightly different then what's in the rules, and seemed to play out just fine.