Das Problem ist jetzt gelöst.
Ich habe mich bei iCloud komplett abgemeldet, d.h alle Haken entfernt und dann jeweils den Rechner neu gestartet und, als das so noch nichts gebracht hat, den Vorgang dann wiederholt.
Dann war beim zweiten Mal bei den Nachrichten die Einstellung "Nachrichten in iCloud synchronisieren" sichtbar.
Der Sync funktioniert jetzt auch mit allen Geräten.