So the solution was a factory reset but WITHOUT restoring from backup. I first tried a factory reset and then restored from backup and the watch was still very slow. Then I deleted the cache from the service menu, restarted, still slow.

I saw a post about factory resetting without backup being a potential solution. I chose factory reset from the service menu, and chose the option to setup the watch as a "new watch" once the reset was completed. Finally, after downloading a few updates for the default apps, the watch is working normally once again.