Moin Uli,
Von der Westküste wäre Friedrichstadt einen Abstecher wert.
An der Ostsee würde ich dir zusätzlich zu FL und HL empfehlen, in Kappeln vom Ostseeradweg abzuweichen und an der Schlei entlang nach Schleswig zu fahren. Die Gegend entlang der Schlei ist eine der schönsten und interessantesten (Arnis, Brücke in Lindaunis, Fähre Missunde) Schleswig-Holsteins. Schleswig und Haithabu (Haddeby) sind sowohl historisch als auch architektonisch sehenswert. Von Schleswig dann über Geltorf-Hummelfeld-Osterby nach Eckernförde. Die Touri-Burgen direkt an der Küste (Damp) kann man sich auf dem Abschnitt echt sparen.
Kiel muss man sich nicht unbedingt antun. Die Fähre Strande-Laboe spart den Umweg um die Förde und durch die Stadt.
Fehmarn lohnt den Abstecher, allerdings musst du dich halt über die Brücke "trauen". Empfehlenswert das Wasservogelreservat Wallnau im Südosten der Insel (Jimi Hendrix' letztes Konzert...). Viel Verkehr kann ich so nicht sagen, es gibt halt nur schmale Straßen und im Sommer relativ viele Urlauber.
Richtig schlechte Wege gibt es auf dem Ostsee-RW in SH eigentlich nicht, die kommen erst in MeckPomm. An der Geltinger Bucht siehts
so aus

.
Die Alte Salzstraße hat von Lübeck zur Elbe zwei Trassen. Entweder immer entlang des Elbe-Lübeck-Kanals, ganz nett und interessant, aber auch schnell eintönig, oder mit Schlenker durch die Seenplatte über Ratzeburg. Ich würde die zweite (gut beschilderte) Variane fahren.
Viel Text, ich hoffe es hilft. Übrigens, wenn ich Zeit hätte, würde ich die Tour mitfahren, auch wenn ich fast 100% davon kenne...