What steps do I need to take to replace my Apple TV 4 remote?
Make sure the old Apple TV Remote is out of Bluetooth range, then while in front of the Apple TV set top box press a button on the new remote. This should pair the remote to the Apple TV.

If not, try pressing Volume Up and Menu simultaneously on both remotes for 2-3 seconds, new and old, then do the aforementioned steps again with the new remote.