Same problem here. The watch is obviously connected. Otherwise, your watch wouldn't be able to activate the Google Assistant app on your phone during installation. Just to verify, I even used the Find My Phone function on the watch and sure enough, the phone rang. And yes, every other Bluetooth related app communicates just fine, e.g. Samsung Health. So clearly, the watch is connected to my phone through Bluetooth and the error message is wrong.
This is a known bug. If you search on it, you'll find many complaints but still no official acknowledgement from Samsung or Google. I've tried all suggested solutions, e.g. resetting and reinstallations, but nothing has worked.
Ditto. I tried all that too and it still won't connect. Glad to know I'm not unique. I guess the best thing to do is to wait for an official statement from Samsung and see if there is an update that fixes everything.