Para quitar y poner a todos los +34 delante hay un truco fácil.
1) Exportas a CSV todos los contactos
2) Conectar al ordenador el móvil y abres con un editor de texto (notepads o similares) el archivo .CSV (que te lo habrá dejado en la SD) y los cambias todos a saco. Con un replace (no uno a uno, claro)
3) Borras toda tu agenda de contactos en el móvil
4) Importas de nuevo el CSV que has modificado a mano
Como siempre con los backups, no modifiques el CSV directamente, haz una copia y modfica la copia, por si acaso.