TL;DR: It isn't the sync that's broken, it's the sync progress updates in the app.
Here's my update from Audible:
Thanks so much for your reply. We have actually found more about the issue. Since you took the time to send us that information, let me give you a bit more insight of what we have found.
What seems to be broken is the progress updates. The book, even if it shows at 0%, will sync. The error "Apple Watch is not responding" is actually an expected behavior of this situation. After 40 seconds of receiving no progress update, that error will pop up. There is only one moment where the progress will be synced, and that is when the book is completely synced. In simple terms, the books will sync even if the screen shows they are not syncing. Once the sync process finished, you will see the only update of the sync, letting you know the issue is fixed. We are still working on making the sync progress update more frequently, and will keep you update for when we have a resolution.
So, the voodoo
@Frederiksberg discovered wasn't the "turn off screen" part, it was the "left on charger overnight" part! I.e. just leave the Watch to sync and it will sync even if there is a "watch not pairing" error message. I kept cancelling the sync when I saw the error message. Once I stoped cancelling, the syncs proceeded just fine.
So now I have lots of books synced. But how frustrating! Makes me glad I make art and don't do software development/debugging.
I do give credit to Audible for great customer service on this one though.