Experienced the same issue initially. Received a new Apple Watch (series 7) yesterday and tried to set up the Remote app on the watch to control Apple TV (4th generation). I tried many sproposed olutions (pair/re-pair watch and iphone; delete Remote app from Watch, then re-install; ensure latest software is installed on everything... did not work).
After some tinkering, I got it to work as follows: I realized that my iPhone was NOT paired with my Apple TV.
Of course, make sure everything (Watch, iPhone, Apple TV) is all on the same wifi network.
Also make sure the Remote app is installed on the Watch first. Keep the app open while performing the steps below.
On the Apple TV - Go to Settings - Remotes and Devices - Remote App and Devices.
Bring your iPhone close to the Apple TV console. When you see a message on your iOS device that says Pair Apple TV, tap Pair. You will see a code appear on your TV screen - enter that code onto your iPhone.
Your iPhone (which should have been connected to your Apple Watch from the start) is now paired with your Apple TV.
For me, once the iPhone was paired with the Apple TV, it automatically triggered the Remote app on the Apple Watch to work!
Hope this helps.