No mater what I tried, the option to enable the developer mode on my watch just wouldn't show up. What made the difference for me, is connecting the phone to the Mac via the cable. After that my watch showed up in the Devices window in Xcode and I was able to enable developer mode on the watch itself.

Got a brand new Mac and a brand new watch. Existing iPhone already has developer mode enabled. Connect iPhone to the Mac with the cable. Click "Trust this computer". in Xcode, click Window | Devices and Simulators. The iPhone already shows up there. Add and set it up. The watch still wouldn't show up. Developer mode option is absent in Settings | Privacy & Security. Doing some random things like restarting Xcode and the watch. Still no Developer mode option on the watch. Then I noticed a popup - something about updating my iPhone or Xcode to enable development. Unfortunately I don't remember the exact message. Do the update. I am not sure if that was it, but after update, Developer mode option finally shows up on the watch. Enable Developer mode, the watch will restart, then confirm enablement on the watch again. In Xcode go to Window | Devices. The watch now shows up there. Add and set it up. It failed a few times along the way. Retried and eventually it worked. Create a test watchOS project in Xcode. I did watch only, no companion app. Select your team for code signing certificate while creating the project. Select your watch as run target and run the project. It works!