Wieso nicht von Skagen über die Vestkystruten südwärts? Dort ist's nicht allzu heiss, die Route ist verkehrsfrei bzw. -arm, es hat nicht viele Steigungen, und Infrastruktur hat's zur Genüge. Und vor allem: die Strecke ist wirklich abwechlungsreich! Bloss der Wind kann heftig sein, und man muss Schotter mögen. Hier gibt's ein paar Bilder vom Mai.
An Esbjerg könnt ihr Inselhüpfen und am Ende, wenn ihr noch nicht genug habt, durch die Niederlande gondeln.
Anreise nach Skagen geht mit den Fähren nach Göteborg und Frederikshavn ganz einfach. Frederikshavn - Skagen würde ich mit dem Zug zurücklegen, denn die Veloroute führt dort der Hauptstrasse entlang.

Finnland und Schweden stelle ich mir ein bisschen eintönig vor bei euren Tageskilometern, und bei eurem Tempo könnt ihr auch den u.U. zahlreich vorhandenen Plagegeistern nicht davonfahren.