The issue is now resolved, and the problem was neither in Core Data, nor in code / CloudKit. Simply the iCloud storage was full. But I didn't know that, because it was an account of the QA team member, not mine. And this is extremely tricky. So I want to keep this thread, and I will describe now how it was solved:
Returned to the version where none of the solutions listed in the original message were implemented.
Managed to isolate the issue only for macOS by resetting the CloudKit environment and deploying the schema changes (worked for devices connected to my account).
Solved the issue for macOS by following the step 2 of the original message. Yes, as many people mentioned, seems it is crucial to have this framework added (worked for devices connected to my account).
Analysed the CloudKit dashboard (Telemetry) and got two know that at least 10 errors in the last half an hour came with the label "QUOTA_EXCEEDED".
And that was it, next minute it all was clear for me. After they've emptied some space in their iCloud, the issue was resolved.
Cheers,