Issue solved!
I solved the issue by changing the synchronization mode to a different cloud service and then reselecting iCloud, providing all the authentication details and submitting the form. The iPhones now have a stable connection to iCloud and sync continuously. I will try the same on the Macbooks when they loose their authentication again.
----
Edit: Works like a charm now on iPhones and Macbooks!