I now did a complete reinstall of Ubuntu.
The first thing I downloaded was Insync.
I unchecked nearly all folders in the Insync OneDrive Setup screen, and the downloading worked fine.
For testing I then copied some video files in the root directory of the synced OneDrive folder to test the uploading. This are about 10 files in the range of 1MB to 14MB, with one file having 27 MB.
The uploading seemed faster than before and all files were successfully uploaded except the one with 27 MB which again gave me the “The cloud is temporarily unavailable or under maintenance” error.
After all smaller files were uploaded I pressed the “Retry” button and this time the upload bar for the file with 27 MB filled fully. But then something stranger happened: Instead of the file now being uploaded, the uploading bar disappeared and reappeared empty again after a few second. So now it seems to be stuck in a loop trying to upload this one file with 27 MB, always completely filling the upload bar but never successfully uploading it to OneDrive and not raising any errors.
Maybe I have a special situation - OneDrive Germany (which apparently is something different than consumer OneDrive for other countries due to privacy laws) and pretty slow internet (rural Bavaria).