I've had this happen a few times. The way it goes is that everything is working, then one day I try to deploy an app to my watch and Xcode and just says "Waiting to reconnect to Watch" (or something like that) forever (or at least longer than I'm willing to wait). I unpair my watch from Xcode, and when I try to re-pair it, it doesn't show up. As others have said, restarting every device doesn't help. After just spending another hour+ of my life trying to figure this out, I got it to show up by unpairing everything from Xcode, turning off Developer Mode (under Privacy & Security) on the Apple Watch and the iPhone (turning it off on just Apple Watch doesn't work), then turning it back on (which requires restarts on each device) Once that was done done, the phone and watch showed up in Devices & Simulators again, and I could re-pair them.

I also have a Watch-Only app that was newly created from the Watch-Only Xcode template. It was rejected on its first App Review submission for the same reason. Based on the discussions I've found here and elsewhere, it seems that the issue is that App Review isn't recognizing it as a Watch-Only app. After the rejection, I responded with the following comment and then re-submitted without uploading a new binary. Soon after, it was accepted. My suggestion would be to mention in the App Review instructions that it's a Watch-Only app, as it appears this may not be clear on their side. Here was my reply following the initial rejection due to 'Accurate Metadata / UIRequiredDeviceCapabilities': 'This is a Watch-Only app created using the Xcode Watch-Only template. Could you please verify that you're attempting to install it as a Watch-Only app? If so, could you link to documentation that specifies what UIRequiredDeviceCapabilities should be set for a Watch-Only app? Thank you.'