Pairing Apple Watch series 4 with Bluetooth headphones

Just to ask the silly question, but did you put the Bluetooth devices into "Discovery Mode"

I've paired 4 different Bluetooth headphones with my Apple Watch. The only trivial one was my Apple AirPods. But I've paired Sony Noise Canceling headphones, 15 year old Jabra headphones, and 15 year old Insignia Bluetooth headphones.

And for the last 3, I had to Google to find out how I put the headphones into Bluetooth Discovery Mode.

Wiping and reinstalling all software seems excessive as a first step. I suggest you take a look at these two support docs, and see if they get you working without the time consuming trauma of a full reload.

About Bluetooth, Wi-Fi, and cellular on your Apple Watch - Apple Support

Use Bluetooth accessories with Apple Watch - Apple Support

If your Apple Watch still can't connect, unpair your devices, then pair them again:

• On your Apple Watch, tap Settings > General > Reset > Erase All Content and Settings.
• On your iPhone, open the Apple Watch app, tap the My Watch tab, then tap your watch at the top of the screen. ... 
• Pair your Apple Watch and iPhone again.