En principio no parece dificil, aunque si algo complicado.
Hay un punto clave que no cuentas, que es cuándo le llegan los datos al Arduino. Si para recibir los datos antes los ha de pedir, entonces es bastante sencillo: lees secuencialmente cada uno de los GPS, guardado cada envío en un array, reformateas los datos y los reenvías.
Si en lugar de bajo demanda los datos llegan según los GPS los van cantando, entonces si que habría que hacer un poco más de trabajo, tal vez usando interrupciones, pero tampoco mucho más.
Las velocidades de transmisión dan igual, simplemente adaptas cada puerto a cada dispositivo y listos.
Ah, y te hará falta el Arduino Mega, que tiene 4 puertos serie, el Uno, el barato, solo tiene uno.