Thanks to a bad translation for the original German... it turns out that I've been playing this game slightly wrong for years... but I actually think it works slightly better!
Use a variant of the 7-player distribution system for games of 4-6 players. In other words, turn one less card face-up during distribution, and instead place this card face-DOWN just to the right of the King. The King now chooses his role from the remaining cards, which should be equal to the number of players.
Continue as normal, until the last player is passed only ONE card... but he/she gets to choose between that card and the previously mentioned face-DOWN card, which only he/she has seen. The unchosen card is placed face-down, out of play, as normal.
This removes some of the knowledge from the King, as far as what is actually out of play, and creates a bit more guesswork as far as who might have which character.
Try it out, and I'd be interested in any impressions that people have from your experience.