Vielleicht hilft dir der EC151 (Frankfurt ab 8.01-Milano an 15.35)? Danach gibt es wiederum direkte Züge nach Genua, wo es dann je nach Fahrplan noch auf eine Nachtfähre nach Bastia reicht... Bezüglich Velomitnahme in Italien weiss ich zwar nichts.

Oder es gibt auch Fähren ab Marseille oder Toulon? Vielleicht wäre das auch eine zu prüfende Option?

EDIT:
Sehe gerade, der Bahnhof in Genua liegt in Fussdistanz vom Hafen. Wenn also der Verkehr zu heftig wäre, könnte man wohl auch problemlos zur Fähre schieben...