Hola,
No es necesario enviar un nuevo sitemap por lo que se refiere a las redirecciones.
Las redirecciones las puedes hacer directamente en htaccess, hay mucha info por el foro y en todo internet. También puedes crear un archivo php con un array donde incluyes las urls nueva y antígua y le indicas que haga un redirec 301, tendrías que subir el archivo a la raiz e incluirlo en el index, parece complicado pero es fácil.
Yo tengo la segunda opción en ps 1.6 y con un modulo editor modifico el archivo desde el admin de prestashop y me resulta cómodo a la hora de añadir o modificar urls.