Just bought Apple Watch and it has Activation Lock.

I would not expect this when purchasing from Walmart directly, but these cases seemingly can arise with other resellers, whether those others are reselling though a Walmart, or eBay, or Amazon, or NewEgg, or Facebook Marketplace, or other such sales websites.

If this was Walmart, they sold a not-new product as new. You’ll want to discuss this directly with them.

You seem to have got scammed, regardless.

Nobody here can help with Activation Lock, and Apple won’t help absent sufficiently convincing proof of ownership.

Contact Apple Support. Here is how to start an Activation Lock service request: How to remove Activation Lock - Apple Support

Return the watch to Walmart! It obviously is not new as it has someone else's Activation Lock on it...

They sold you a used product advertised as new, that is illegal. Threaten to call corporate and see if they change their tune.