HSV-Steph Exzellent! Genau das wäre auch mein nächster Schritt gewesen. Schrittweises rantasten an den/die "Bösewicht/er" 
Nun bin ich an dem Punkt an dem ich gestern Mittag schon war.
Rein funktionell betrachtet magst du da recht haben, aber den vorgeschlagenen "Versuchsaufbau" hatte ich zumindest nur als reine Fehleranalyse verstanden, um einzugrenzen, woher dein Fehler herrührt. Deshalb kann ich dein "Verzagen" auch überhaupt nicht nachvollziehen, denn deine Berichterstattung gibt wertvolle Hinweise zur Fehlereingrenzung. Nebenbei bemerkt habe ich dir einen Tipp zur Herangehensweise bereits vor 16 Tagen gegeben 
Wenn ich dich also richtig verstanden habe, funktioniert 1 ATV über LAN wie gewünscht, d.h. es meldet sich in HomeKit als verbunden an. Wie HSV-Steph aus meiner Sicht nun folgerichtig vorschlägt, wäre der nächste logische und vor allem unaufwändige Schritt das Testen des 2. ATV – und NUR dieses – über LAN. Wenn dasselbe sich ebenfalls als verbundene Steuerzentrale auszeichnet, kann man also schonmal einen Defekt oder eine Fehlkonfiguration bei beiden ATV ausschließen = 1. wichtige Erkenntnis.
Nun kann schnell die nächste Anordnung ausprobiert werden, nämlich beide ATV über LAN direkt an den Router anzuschließen, um festzustellen, ob sich im Verbund die beiden Steuerzentralen korrekt in HomeKit verhalten, also ob genau 1 ATV stabil als verbunden und 1 ATV als Standby angezeigt wird. Es spielt dabei übrigens erstmal überhaupt keine Rolle, ob dabei diverse HomeKit-Geräte als unerreichbar angezeigt werden, weswegen du beide ATV auch versuchsweise mit kurzen LAN-Kabeln im Routerraum testen kannst. Das macht so gut wie keinen Zusatzaufwand und gibt weitere wertvolle Hinweise.
Ich erinnere mich, dass du Bluetooth- Geräte einsetzt, weswegen bei größeren Distanzen dafür natürlich die ATV quasi als Hubs benötigt werden und es völlig normal ist, dass, wenn du ein ATV aus dem Einzugsbereich dieser Geräte entfernst, dieselben nicht mehr erreichbar sind. Interessant bei diesem Test ist ausschließlich der Status der Steuerzentralen in HomeKit!
Mein Verdacht verdichtet sich inzwischen zusehend, dass deine Fritzbox aufgrund der veralteten Firmware und der zusätzlichen Sperrung durch Vodafone im aktuellen HomeKit-Verbund kein zuverlässiges Gerät (mehr) abgibt. Insbesondere eine WLAN-Verbindung ist allein schon aufgrund von Sicherheitsabfragen erheblich aufwändiger und anfälliger als eine LAN-Verbindung, weswegen sich auch die WLAN-Verbindungsqualität nach dem Update auf iOS 13x verändert haben könnte. Da derartige Details weder von Apple noch von AVM (schon gar nicht von Vodafone) angegeben werden, ist das ganze Theoretisieren auch nur ein Tappen im Dunkeln, bzw. eine Abwägung mit den eigenen Erfahrungen.
Ich lehne mich mal aus dem Fenster und sage vorher, dass sich für die letztgenannte Anordnung beide Steuerzentralen über LAN korrekt verhalten. Damit wäre die 3. wichtige Erkenntnis: Dein Problem ist die WLAN-Verbindung, respektive die Fritzbox. Aber das ist zum jetzigen Zeitpunkt noch reine Spekulation.
Wie gesagt, mit 2 vergleichsweise unaufwändigen Tests kannst du sehr viel herausfinden. Wenn sich meine Vorhersage als falsch erweist, gibt’s weitere Ideen… 