Glad you got it working and thanks for posting the video for all of us. I have tried logging in and out of iCloud to no prevail. I have all but given up on this working until next beta. Beta 2 on the watch isn't behaving very well anyways.
EDIT: wow after actually watching the video it works rather fast and makes me really want mine to work... I am flying out for work tomorrow morning though and simply don't have time to try and do a full fresh install of Sierra. Maybe I need to unpaid and repair my watch... /frustrated
I unpaired and re-paired my watch no difference.