Apple watch locked

My apple watch is locked, will not pair with my new iPhone. Message on the iWatch is “wrong passcode. Open the apple watch app on your iPhone, go to passcode, then tap re-enable passcode entry to try again”. I cannot get past this message on my iWatch. My new iPhone has never been connected with the watch and doesn’t have menu for Passcode until first paired.