Ich hab deinen und den Nachbarfaden mal zum Anlass genommen, mich über die Bahnverbindungen ohne Umsteige und mit unverpackten Rädern zu informieren. (allerdings Anfang Januar)
Strassbourg . Montpellier Saint-Roch durchgehend mit TGV
Montpellier Saint-Roch . Bordeaux mit TGV
Bordeaux . Hendaye mit TER

https://www.sncf-connect.com/de-de/

Dann radelst Du über die Grenze, leihst dir nen Berlingo oder was ähnliches, gibst den in Cadiz ab und schipperst nach Gran Canaria und Fuerteventura.