Your iPhone can support multiple paired Bluetooth devices of different types (AirPods, Apple Watch, Car Audio, other audio device, smart TV are on mine) and it can also support multiple different Apple Watches being paired at the same time (but only one can be active). So it looks like your iPhone should support your hopes.
Your post implies that your Apple Watch is working correctly and paired to your iPhone, which indicates the iPhone's Bluetooth function is working OK. The fact that the third party watch will not pair at all suggests it might have a problem, but there is no indication so far whether this is a hardware failure or something in software.
Try to remember whether this problem follows after any of the recent software updates from Apple. It is possible you might need an update for the Fossil HR's iPhone app or even the device's firmware. Check the App Store or other download source for the Fossil software.