I too was having the same issue. Using
adb logcat, I saw the following lines repeating during the failing setup step:
WearSetup: [WatchConnectionStep] Force enabling connection for ConnectionConfiguration[ Name=Google Pixel Watch 0XXX, Address=XX:XX:XX:XX:XX:XX:XX, Type=5, Role=1, Enabled=true, IsConnected=false, PeerNodeId=null, BtlePriority=true, NodeId=null, PackageName=null, ConnectionRetryStrategy=0, allowedConfigPackages=null, Migrating=false]
WearSetup: [WatchConnectionStep] Connected configuration not found, retrying in 3000
which repeated for a few times until the setup timed out and I was told to factory reset the watch.
I fixed it by allowing the 'Nearby Devices' permission to the Google Play Services app in Settings.
Settings > Privacy > Permissions Manager > Nearby devices > Google Play Services > Allowed.