Are you sure they said "stolen"? A device can be marked as "lost" but not stolen unless Apple has some kind of links to police or insurance databases (and I have never heard of that).
Is this a Watch you just bought; and from whom did you buy it? -- somebody reputable??
Read about how to use Lost Mode in Find Devices on iCloud.com
Use Lost Mode in Find Devices on iCloud.com - Apple Support
When you find your lost device, do either of the following to turn off Lost Mode:
- You can turn off Lost Mode by entering your passcode on the device.
- In Find Devices on iCloud.com, click All Devices, then select the device that’s in Lost Mode. Click Lost Mode, click Stop Lost Mode, then click Stop Lost Mode again.
If this is a used Watch and just new to you, there is indeed the possibility it was stolen unless you trust the seller. If it was stolen there is nothing you can do about that other than to ask the seller for a refund.