This drove me nuts for a bit. I've now paired successfully with my Watch, two iPhones, and two iPads.
The step that most of the posts here seem to be missing is to completely disable Home Sharing within the iOS app. To do that, tap on settings (upper right corner) and then tap or slide the slider to turn it off. On most of my devices, this kicked you back to the main screen, and asked if you wanted to set up a new library via Home Sharing (large, prominent, blue button) or manually (listed below that). Tap on manually, which will bring up a screen with a four-digit code. Once you've done that, then the device will show up within Music, listed on that left-most window as a "Devices" (listed underneath iTunes Store for me, but if you kept the default view, it should be underneath the "Library" subheading, or specifically, Music Videos). Click on the device, which will bring you to a screen allowing the entry of the four digits.
Of note, one iPad (an older, iPad Air 2) seemed to hang the app when trying to disable Home Sharing. I had to uninstall the app and then re-download and install it to get it working.
The Apple Watch worked properly once I had fixed the iPhone it was paired to. In that case, just trying to add a new library on the Watch caused it to appear within the Music app.
Happy with Apple for bringing back this functionality. It's a bit rocky - more than I'd expect from Apple - but I'll take what I can get.