Some Bluetooth devices require that you manually do something to send the pairing signal; something like push a button on the device.
The fact that your iMac saw them immediately might refute what I just said, but check the manual for the headphones and see if you can do something.
Update: according to a YouTube video, if you press and hold the power button, you should see a flashing blue light on your headphones; this is the Bluetooth pairing mode. At least on the video, the headphones then showed up under "Other Devices" on an iPhone.
On a Mac since 1984.
Currently: 27" iMacs, Macbook Air, macOS 10.15.x,; iPhones, iPods and iPads galore!