Actually I was having the same problem and discovered why. In the News app itself there are some notification settings. Why it's so obscure and hard to find is unlike Apple, but it's there all the same.
Go to the News app and tap on the Favorites tab. At the very top you'll see three things: a bell gliph, a Favorites option (for sorting), and an Edit button. Tap on the bell gliph. It's for configuring the notifications.

From there it's pretty self explanatory. You can turn on or off all notifications right there. It doesn't explicitly say Apple Watch notifications, but they are somehow intrinsically connected. I disabled all of them and it stopped harassing me on my watch.
They really should make the notification options separate for iOS and the watch. Seems dumb how I have to go in to a place that makes no sense just to turn off stuff.
Incidentally you can also stop the annoying barrage of default news sources here on the Favorites screen. Just hit Edit and remove them.