Weird bug...same thing was happening to me on Apple Watch Series 3 and iPhone 11 Pro. Had to remove/unpair the apple watch from everything on my phone (icloud, watch app, etc.) update to iOS 15.1, hard reset the phone and watch. THEN - put the iPhone on low power mode and turned off wifi assist (settings->cellular->wifi assist) and paired the watch manually, and it finally worked. Hope this helps.