I got a new phone after mine was stolen, and I can't pair my apple watch with new phone

First question, did you setup the new phone on your original Apple ID?

(You should have done but many try making a new ID for the new phone. This brings you into conflict with Activation Lock).

If you are sure you have the correct login parameters for your Apple ID, use a web browser to go to https://appleid.apple.com and login there (this also checks for Operator Error entering the ID or password). You should see all your devices including the Apple Watch which is resisting. If you don't see the watch either you have deleted it from your ID, or you have managed to get 2 Apple IDs with the watch on the other one :(

If you have confirmed your Apple ID and login details that leaves fat-finger problems entering the ID and password for the watch setup, -or- as happened to me setting up my new watch last week, the server is well overloaded checking all the new setups and it just timed out several times before I finally got it right. Keep trying if you think this is the case.

You can ask apple to remove the activation lock online on this page;

Online Activation Lock Removal Tool.

Or this;

If you can't remember/gain access to the apple id that paired the watch to the phone.Take the watch and it's receipt along with some photo id and any other proof of ownership to an Apple Store and request that they remove the Activation Lock for you.