Most BT LE devices should work, but some work better than others. Price seems to not be a factor as the cheaper ones often seem to work better than the expensive ones. This is due to the fact that cheap models are more likely to use the base BT protocols and not customize them for advanced features or settings like more expensive models do (and there is no way of knowing if a manufacturer has tweaked the protocols to take them out of compliance). The BT standard is in such a way a 'standard' that it can be widely interpreted with different settings for buffer sizes, time outs, profiles, protocols, antenna configurations, etc.. TomTom cannot change their code every time a manufacturers messes with the BT coding. This is a case where paying more will not increase the chances of connectivity, it may actually decrease it. There are thousands of models out there so there is no way for TT to test them all and since the manufacturers often tweak the BT settings there is no way to know upfront if a pair will work or not. At a minimum they need to be BT LE and support A2DP and AVRCP, the two protocols necessary to play music. Your best bet is to buy them from someplace with a good return policy so if they don't work you can return them and try another brand.
Before pairing, you should turn off BT on all the other devices you have tried pairing them to, as BT is a one-to-one relationship so it can only play on one device at a time. Any of these devices could be stealing the signal first. Alternately, go outside away from the other devices so they are all out of range before trying to pair the headphones. Make sure the headphones are in pairing mode while on the clock screen and then press up to have the watch search for it (don't go into search mode on the watch first). On most headphones you need to press and hold the power button for an extended period to get into pairing (check the instructions for your headphones). Once they are paired you do not need to pair again, but make sure the headphones are turned on while on the clock screen and then press up to have the watch search for it (don't go into search mode on the watch first). This works for me every time. If I do it the other way and got to search first it often won’t find them. Finally, make sure you are not putting the headphones into pairing each time. On some models if you hold the power button for a second too long it will put it into pairing mode. For pairing purposes, leave the headphones sitting on the watch so they are as close as possible. And again, make sure you are in clock mode before going into pairing mode (just like when you turn them on to listen) and only press up once you have gotten the confirmation from the headphones that they are in pairing mode.
I hope this helped answer your question. If so, please mark it as a solution so others can look for it if they have the same question.