Ich konnte das Problem bei mir mittlerweile lösen. Mir wurde in der Facebook Gruppe "Apple iPhone Deutschland" geholfen. Ich versuche mal die Anleitung hier rein zu packen:
Jemand: Hast du ein Gerät um den Verifizierungscode zu empfangen? Laut der Fehlermeldung hast du die Zwei-Faktor-Authentifizierung aktiviert, aber kein Gerät um den Code zu empfangen.
Ich: Ich habe nur mein iPhone, sonst nichts.
Jemand: ok und du bekommst auf dem iPhone keinen Code angezeigt? Schaue mal unter Einstellungen -> iCloud -> Erweiterter Datenschutz ob das aktiviert ist. Du kannst auch einmal kurz den Zugriff auf iCloud über
das Internet deaktivieren und wieder aktivieren. Wenn das auch nicht hilft. Dann melde dich einmal ab und wieder an. Also mit deiner id auf dem iPhone.
Ich: erweiterter Datenschutz ist tatsächlich ausgeschaltet auf dem iPhone.  Dann schalte ich das noch mal ein, sobald ich den Laptop anhabe und hoffe, dass ich dann einen Code angezeigt bekomme auf dem iPhone.
Danke schonmal.
Jemand: ich wollte den erweiterten Datenschutz aktivieren, was nicht möglich war, weil ich keinen gerätecode eingerichtet habe. Also habe ich das gemacht und dann wiederum einen weiteren Fehler erhalten, siehe nächstes
Bild.
(Screenshot mit diesem WICHTIGEN Text: Der erweiterte Datenschutz ist nicht verfügbar. Du musst in den Einstellungen dieses Gerätes einen Gerätecode einrichten, bevor du den erweiterten Datenschutz aktivieren kannst. Ein Gerätecode schützt nicht nur das Gerät sondern kann Dir auch bei der Wiedererlangung des Zugriffs auf DEinen Account helfen, falls Du Dein Passwort vergisst").
Ich: Screenshot mit diesem Text: Erweiterter Datenschutz kann nicht aktiviert werden. Versuche es später erneut.
Jemand: hast du dein iPhone schon neugestartet? Und es nochmal probiert? Es kann sein, dass das nur ein vorübergehender Fehler ist.
Ich: ja hab es gestern Abend nach diversen Versuchen und unzähligen weiteren Änderungen diverser Einstellungen hin bekommen. ^^ Habe den erweiterten Datenschutz dann wieder ausgeschaltet und bin gespannt wie es weiter geht.
Schlussendlich lag es bei mir daran, dass ich diesen Code nicht aktiviert hatte.