Mit zerlegtem Rad: Wenn du es bis am Abend nach Paris schaffst, z.B. 05:45 ab Graz, 18:16 an Paris mit einmal Umsteigen, dann gibt es den Intercité-Nachtzug der SNCF nach Perpignan. Der ist relativ günstig. Er fährt zwar nicht an allen Tagen bis Perpignan, aber immer bis Toulouse und man ist trotzdem gegen 11 am Ziel und hat fast noch einen kompletten Tag.

P.S.: Die olympischen Spiele hast du sicher auf dem Schirm. In dieser Zeit würde ich Umsteigen in Paris natürlich nicht empfehlen.