Die erste Frage: Für welches Reisedatum? - Es gibt Unterschiede je nach Jahreszeit (beonders betroffen: die wenigen Nachtzüge noch). Was in diesem Jahr zumindest in der Sommersaison ging, ist folgende Verbindung:

Intercités Bordeaux - Toulouse (Radmitnahme reservierunsgpflichtig, im Gegensatz zum Intercités ab Bayonne). Abfahrt in Bayonne am Nachmittag, müsste für die Variante ab Bordeaux ähnlich sein. Ab Toulouse Nachtzug nach Paris (Radmitnahme kosten-/reservierunsgpflichtig). Eine gute Stunde Zeit für Bahnhofswechsel Austerlitz/Gare de l'Est). Intercités Eco von Paris nach Strasbourg, Ankunft mittags (wohl gegen 13 h) - Radmitnahme auch dort kosten-/reservierungspflichtig. Ab Straßburg dann mit Ortenau-Bahn nach Appenweier oder Offenburg (Radmitnahme kostenlos), dann bundesdeutscher Fernverkehr. Brutto wohl so 24-26 h bis Koblenz oder so.

Varianten: Zwischen Paris und Bordeaux findest du TGVs mit Radmitnahme. Um den Intercités Eco nach Strasburg zu erreichen, müsstest du aber in Paris übernachten. Gesamtfahrzeit dürfte damit etwas kürzer kommen, aber mit Übernachtung in Paris natürlich teurer im Geldsäckel. Eine weitere Variante ist zwischen Straßburg und der dt. Oberheinschiene zu radeln (z.B. nach Bühl oder Rastatt). Dann abends Fernverkehrszug an den Mittelrhein. So würde man nicht den ganzen Tag aneinander im Zug sitzen.

Versuch aber nicht, eine derartige Verbindung für nächsten Sommer auszutüfteln. Da ist vermutlich alles wieder etwas anders - die SNCF ist da ziemlich flexibel über die Jahre hinweg.