The devices can ship with an embedded hardware security module that holds a private key. The private key has its public key whitelisted by Rolex, and can be used to sign a message transferring the ownership to the current owner's public key. If you can do this transfer action, the device is legitimate. Of course you'd need to check that the public keys/addresses match Rolex's.

Synchronisation is the hard part. I suppose there are a few different ways to do it. One way would be to use a hardware that holds a private key in a secure chip, and whoever has access to the physical watch can sign a message with that key to point to an arbitrary address. This can then be submitted to the blockchain. Confirmation is easy, as the blockchain takes care of that. It would be emitted by a verifiable/trusted public key. If the address is not Rolex's address, the item is fake.