Ich habe die Lösung des Problems gefunden:
Schritt 1: Vorwahl aller Kontakte vor die Nummer stellen
Schritt 2: SMS Backup erstellen
Schritt 3: SMS Backup bearbeiten (vor alle Nummern die richtige Vorwahl einstellen (kann lange dauern, am besten mit "suchen und ersetzen"))
Schritt 4: Alle SMS auf dem Handy löschen
Schritt 5: SMS wiederherstellen
Hinweis: Für das SMS Backup ist MIUI-Backup leider nicht geeignet!