Oculus writes, that they require the Apps Facebook App Installer and Facebook App Manager, and ask that you re-enable them (https://support.oculus.com/help/oculus/186299228426214).
If that worked, then great. But those two programs were not in my App Manager (even when activating "show all").
I tried everything, like re-installing every app with name containing Samsung Gear VR, Oculus and Facebook. Still, the two apps were missing.
I searched the web and found these two sources:
I installed them and got no warning messages from ES File Manager. I can give no guarantee that they are safe and am looking forward to what the experts found out. After installing them, the Oculus App was able to install the updates and it now works in Gear VR as normal.
For those who want to try this: download the apk's, place them on the phone (e.g. the Download directory), open and install them with ES File Manager. Then open the Oculus App and start its update which is now working.