To round off this thread: As I wrote in the next last post, automatic updates suddenly started to work for me. Manual updates and new installations were still blocked though. I left it like that for a few days, and gradually more and more apps got updated in the background. When the list of waiting updates was down to two (from originally 18), I tried to manually update those, and it worked! Now, I can also install new apps. And the indicated free space has somehow also increased in this process, to some 680 Mb.
So in conclusion, thanks for the tips but the problem seems to have solved itself, just as mysteriously as it first appeared.