Hi AYohann05
Welcome to the Apple (user-to-user) Community.
Re: "Pairing Apple Watch to new iPhone without the old one and without losing data"
Sorry to hear you were robbed of your iPhone.
Seems the only way to un-pair a Watch from a phone you no longer have, is to erase the Watch. I may be wrong.
Wondering if Apple support's online article (link below) may be at all helpful:
As it is a new phone to the Watch:
How to pair your Apple Watch with a new iPhone - Apple Support
If needed: Watch Support website (info. / support / contact)
Eg: There is a "Get Support" link (online chat / phone / email / etc.) or an app you can download:
(scroll to the very bottom) on their webpage (link below)
Apple Watch - Official Apple Support
All the best :-)