Assuming that they set out in March, traveling by foot only, it would have taken a Roman army 59 days to march from Rome to Lutetia (as the city was known before the 3rd century).

If you allow them to travel by naval convoy for part of it, the journey could have been made in 26 days.

There's a really neat map program called ORBIS which calculates how long journeys between any of 751 Roman sites would have taken and allows you to adjust variables like month of departure, means of transportation, civilian or military, and price. It's really fun to play around with. It's hosted here.

If you ever have a question like this again, allow me to introduce you to ORBIS: this is Google Maps for the high Roman empire and it gives so much information about travel in antiquity. Here is an image of the march from Rome to Lutetia (Roman Paris). The yellow line shows the land route you asked about. Note how much farther the distance is in antiquity. They would have marched 1600 km and it would have taken almost 60 days. Also not how much food they would eat on the way there! The purple route is the fastest route and a common route used by Rome: sail to Massilia (Marseille) and march from there. It saves about 20 days!

Inheritance of Rome by Chris Wickham states on page 26 that in the late Empire, "to travel from Rome to northern Gaul took a minimum of three weeks, an army would take much longer". Julius Caesar, in the late Republic, was able to march 1,500 miles/2,400 km from Rome to Obulco (in Spain) in less than one month, which was and is considered an impressive feat.

I'd note that the maximum march distance will be affected by various factors such as the type of baggage travelling with the army and the season (how much daylight is available).

A large slow train will impede the army and keep them from moving at their top speed. Less daylight means less time to march each day (though armies usually didn't move in the winter). You also can't march the whole day as you need to allow time for the soldiers to setup camp and also cook their dinner.

Lastly the larger the army, the less time you have to march - if its large enough there could be an hour delay between when the front of the column starts and when the tail end finally starts to move. For example a 10,000 man army marching in a 6-wide column would stretch 1.5km and that doesn't account for breaks between units or the baggage. You need to ensure your march distance isn't so long that the tail end of your army isn't arriving in camp after dark.

I'd also note that your march distance could also be influenced by good camp sites. If you've got a good water source 15km away and then the next one is 25km then you'll travel a shorter distance to take advantage of the first location.