This is working just fine for me with my BE NUC.
You definitely have Bluetooth or you wouldn't have been able to pair with the NUC. Have you tried going to the Sound settings and actually choosing the headphones as the output device? Or are the headphones not in the list of devices? If the headphones are not in the list, are you sure you have actually paired with the NUC?
Are you seeing a big red X over top of the icon or is this X part of the icon? A big red X over top of the icon is an indication that the device has been disabled or something similar. In this case, check Device Manager for an issue. If, on the other hand, this is a case where there are simply no speakers or headphones available to output sound to, the icon will change to one that includes a (smaller) X within it.
If you have paired, your Bluetooth is working. The headphones should have been connected during the pairing operation and the current sound output device changed to be the headphones. I saw a somewhat similar (paired but not connected) problem in my main PC when I switched from using a Bluetooth USB dongle to using the Bluetooth on an AX200 card that I was adding. In that case, I deleted the entry(s) for all previous Bluetooth device pairing(s), rebooted, and then went through the process of pairing again. Again, remember that, during the session in which the pairing is done, it should also be connecting and output to the headphones should be automatically enabled.
Hope this helps,