Vagabond8630 It's an old post, but it was useful to me today and may be useful to others.
As you you mentioned, my impediment was nearby devices, but for Play Services.
My symptoms were that after the initial pairing, the 'Getting ready to connect' stage would crap out after about 85%, returning me to the 'Scan for devices' screen. Knowing this, I'll now experiment further with permissions.
Galaxy Watch 5 Pro. Thanks for taking the time to reply, all - you saved me from binning a perfectly good watch.