The problem MAY be related to being connected to 5GHz Wi-Fi. I was stuck in the reported loop and tried several of the suggestions to no avail. After resetting Network Settings on the phone, the problem persisted on the 5GHz connection (which I tried first), but on the 2.5GHz connection, the update download proceeded.
iPhone 11, watch series 4.