This is the first time I've read this. Unfortunately, there are also no directly explanatory "network voices". I would try the following:
- Test with another Mac (if possible)
- MacOS update (if available) -on the affected Mac
- iOS update (if available) -on the corresponding iPhone
- Restart the Notes app on the devices (exit via AppManager, restart) (done as you wrote)
- Deactivate iCloud Sync on the affected Mac (wait for implementation)
- Restart the Mac
- Activate iCloud sync on the Mac (wait for full implementation)
If the problem still persists, I would report it to Apple Support then.
Hint: When deactivating iCloud sync, please note that this signifies deleting all notes and completely redownloading them from the cloud (depending on the number of notes, this indicates a lot of traffic and takes time).
Good luck!