Unauthorised Bluetooth device keeps connecting to Mac

After almost an entire day of experiments and investigation, I think I might have identified the nature of this strange behaviour. The biggest clue (and originally, the most concerning discovery, for obvious reasons) was the relation of the activity of those random devices, with almost 100% certainty, to browser being open.

That's right: the Bluetooth connections weren't happening unless I was actively working in the browser, navigating between pages. This was true for both Safari and Chrome (not Firefox however) but was not the case with Incognito/Private Browsing windows.

Bottom line: it appears that the issue was caused by misbehaving Handoff feature and those random devices trying to connect could have been other people's iOS devices or Macs.

I have no knowledge of how Bluetooth and Bluetooth "sniffing" work, let alone the way Handoff makes use of those, so I can't say what exactly went wrong. By design, Handoff is supposed to only work between the Apple devices that use the same iCloud account, which definitely wasn't the case here.

For the time being, I simply turned Handoff off in the iMac's System Preferences, as well as performed a factory reset of the Bluetooth environment, just in case. I can't yet say if switching Handoff back on after the reset is safe, but will update this answer once I confirm that.