I had the same problem when I tried to set up the watch for the first time.
I then used my wife's old iphone to set up the watch and then there was no issue ( I did not do anything else).
Had both the watch and the phone charging.
So try using another iphone to setup the watch, worked for me.