Wenn die Lösung so einfach gewesen wäre hätte ich mich hier nicht gemeldet. 😉
Der Apple Support konnte mir aber inzwischen helfen.
Seltsamerweise bekam ich zwischendurch die Fehlermeldung das meine Apple-ID für iCloud und iMessage angeblich nicht identisch ist. Ich habe aber nur eine Apple-ID.
Ich musste mich auf allen Geräten ab- und wieder anmelden und dann in den Einstellungen den iCloud Sync sowie auf den iPhone die SMS-Weiterleitung aus- und einschalten.
Danach funktionierte alle wieder, aber eben erst nachdem ich das alles auf allen Geräten gleichzeitig gemacht habe.