Originally Posted by Adlerdriver

Book the tickets separately. Paris-Koln on Thalys.

Get the DB Bahn ticket from Koln-Mainz on line here: http://www.bahn.de/i/view/USA/en/index.shtml

Or just wait until you get to Koln and get the ticket at the station. You can even just get on the train and pay for it w/ the Fedex card once the conductor comes around.