My battery is draining quicker than normal and I don't think my iPhone is consistently communicating to my Apple Watch like it should. I'm not always getting text messages sent to my watch and am missing them on occasion on both devices. A couple days ago, my Apple Watch just suddenly shut down and I couldn't get it to turn back on. I had to hold down the crown and side button until it rebooted. I forgot to mention that I also have Carrot Weather with its complication on my watch screen. It's not always up to date and accurate. Often it has one my my secondary cities which is not my default home city showing.
I am also getting warnings that my iCloud storage is almost full but I don't have anything configured to be backed up except for the bare necessities which don't take up hardly any space. I don't have my photos chosen to be backed up either.
I'm pretty tech savvy and read the troubleshooting posts on this forum all the time. So I know what I should be doing in regards to turing off notifications, background refreshing, raise to wake, screen brightness, etc. I don't have any rouge apps that are phoning home all the time. I tend to wonder if all the iOS updates on top of each other over the year and a half are slowing things down and perhaps a clean install would breath new life into my phone. I want to keep it until the iPhone 8 comes out.
Personally I think the nuclear option of starting over without a restore from iCloud or iTunes is a little extreme and may not resolve the issue, but it sounds like you've weighed your options. I suppose you can always try that and then restore from a backup. Without the restore... If you don't care about what you will lose, and having to install your apps again one by one, then maybe you will end up with both devices functioning normally. If not, then at least you know you have a problem with at least one of your devices.
When did your problems start? With an iOS and WatchOS update? After you installed an app?
Restoring from backup should not actually restore the cruft from all your previous iOS updates (I've been restoring from backup to new iPhones ever since the iPhone 3G). The OS doesn't get backed up. You're just restoring your apps, app data, photos, music, settings, etc. Of course if one of your apps is the problem (usually the case in my experience) there are other ways to deal with that and it sounds like you are aware of reviewing the apps that use battery and background data. I have had apps start to tank my battery life after an update, and the app battery usage has been helpful in identifying the culprit. I wish you could do the same on the watch. Every now and then my watch battery life will tank until I install another round of app updates, and then things return to normal.
I've been using Carrot Weather and Dark Sky for most of the almost 2 years I have had my watch (I prefer Carrot's complications, so that's what is on most of my watch faces). I don't know if either of these were the culprit in my most recent battery life issues, but I only had to live with it for a few days before things returned to normal. Normal activity returned after a bunch of app updates so it could have been any of them that I regularly have docked or as a complication.
The iCloud usage probably isn't a problem, but it's so cheap to get additional iCloud storage. It's worth paying 12 bucks a year to me so I don't have to worry about it, but it's kind of silly that Apple doesn't just start you off with the 50 GB level. Anywho... I try to delete old unused apps from time to time just to cut down on the clutter. I still have an insane amount of apps on my iPhone 6 (I'm a bit of an app junkie). I try a lot of them on my watch as well, but I am much more selective about what I keep on my watch.
Since you have reviewed background data usage for your apps and haven't found any smoking guns, there is a very good chance the problem is simply your iPhone's battery. Every iPhone I have owned gradually degrades in terms of battery. Battery life in Year 2 is never quite what it was in Year 1, and somewhere in Year 3 battery life will get bad enough that it starts to be an inconvenience.
So iPhone battery is one problem, and Watch syncing is another. Sometimes the problem there is the app and not the watch or the phone. Make sure your iOS, WatchOS and apps are up to date. If an app isn't updating regularly for you, try a different one. I use Carrot and I haven't noticed a problem, but then again this time of year where I live it's always cloudy or raining... so I may not notice if the complication isn't up to date.
Sean