Apple Watch will not pair - no internet

When I try to pair my apple watch after performing a factory restore on it the following happens.

-Asks to auto pair

-Finds watch

-Attempts to update software

-Error pops up "Unable to check for update. Checking for a software update failed because you are not connected to the internet."

• Watch has no options other than the pairing screen.
• Connected to internet via Wi-Fi. Internet works in other apps. Please help.