How do I change the Apple ID my watch wants to use?

A new watch should not ask you to use any Apple ID. It should open to the setup screen and offer to pair with your iPhone when you turn it on. And when it pairs to your iPhone, it takes the Apple ID information from your iPhone.

If your new watch doesn't operate at this link portrays, return it to Verizon --> Set up your Apple Watch - Apple Support

Whenever you change ownership always completely wipe the phone back to factory settings.

Simply signing out of one Apple ID and signing in with another always leaves a trail of problems.

What to do before you sell, give away, or trade in your iPhone or iPad - Apple Support

Did you purchase a used Apple Watch?

I'll have to add that to my remedy database! You must have recently changed iPhone ownership or you changed your Apple ID on it?