Welcome to the Forum, @helenamancini! 
I haven’t experienced the particular issue you describe, and the first thing I wonder about is whether any Bluetooth devices will currently connect with your laptop (mice, speakers, etc.). What you’ve detailed so far indicates that the Bluetooth connection is working between your headphones and phone, so it seems like the problem is with the PC, and I wonder if there’s an issue with a corrupt Bluetooth registry entry or something like that on the laptop. What kind of troubleshooting have you done on the Windows machine?
On Windows 10, if I tap the Windows logo/start button and start typing bluetooth, one of the first search options is Find and fix problems with Bluetooth devices, so I’d be curious about the results of running that Bluetooth troubleshooter for starters.
Although you say that you’re current with Windows updates, I wonder about drivers. That’s something else you could check on HP’s Web site to see about available Bluetooth drivers in case you need to update or reinstall those (maybe to a previous version if everything was working well prior to 6 months ago).
The only other thing that immediately occurs to me is whether or not your headphones might be connected to two other devices when you attempt to connect them to the laptop. I mentioned some steps that could be taken to resolve that situation in another post a couple of months ago.