LineageOS update caused permission erros for GApps - Android Q&A, Help & Troubleshooting

Hello together,
I recently made an update of LineageOS for my LG G5 (LineageOS 14.1) as well as my Samsung Galaxy S5 (LineageOS 15.1). They both seem to have serious issues afterwards and I don't know what happened. I assume something has changed within the last month or so and my problem appears with both devices.
It appears as if the permissions for all GApps have changed (or the uids perhaps). All other apps work perfectly fine so far. I also downloaded the latest GApps and installed them via TWRP but that doesn't seem to solve any problem. However I'm not sure that overwrites the old applications or only installs currently not installed ones.
So when ever I use one of these apps (Gmail, Playstore, Maps, some of the system processes), it always crashes and I see the log messages looking like this:
Code:
com.google.android.gms.persistent, PID: 13071
java.lang.RuntimeException: Unable to create application
com.google.android.gms.common.app.GmsApplication:
java.lang.SecurityException: addOnPermissionsChangeListener:
Neither user 10039 nor current process has android.permission.OBSERVE_GRANT_REVOKE_PERMISSIONS.
at android.app.ActivityThread.handleBindApplication(ActivityThread.java:5451)
at android.app.ActivityThread.-wrap2(ActivityThread.java)
at android.app.ActivityThread$H.handleMessage(ActivityThread.java:1564)
at android.os.Handler.dispatchMessage(Handler.java:102)
at android.os.Looper.loop(Looper.java:154)
at android.app.ActivityThread.main(ActivityThread.java:6186)
at java.lang.reflect.Method.invoke(Native Method)
at com.android.internal.os.ZygoteInit$MethodAndArgsCaller.run(ZygoteInit.java:889)
at com.android.internal.os.ZygoteInit.main(ZygoteInit.java:779)
or
Code:
java.lang.SecurityException: Permission Denial: opening provider
com.google.android.gsf.gservices.GservicesProvider from
ProcessRecord{22a7d3b 23968:com.google.android.youtube/u0a108}
(pid=23968, uid=10108) requires com.google.android.providers.gsf.permission.READ_GSERVICES or com.google.android.providers.gsf.permission.WRITE_GSERVICES
at android.os.Parcel.readException(Parcel.java:1684)
at android.os.Parcel.readException(Parcel.java:1637)
at android.app.ActivityManagerProxy.getContentProvider(ActivityManagerNative.java:4199)
or
Code:
java.lang.SecurityException: tname=Sensors - Permission Denial: opening provider com.google.android.gsf.gservices.GservicesProvider from ProcessRecord{3745b29 6048:com.google.android.apps.maps/u0a179} (pid=6048, uid=10179) requires com.google.android.providers.gsf.permission.READ_GSERVICES or com.google.android.providers.gsf.permission.WRITE_GSERVICES
They all have in common that they tell me that "Neither user [???] nor current process has android.permission.[???] "
It seems to work uninstalling the specific app and reinstalling it. However this is a lot of work and isn't really easy for some apps that are closer to the system.
So what can I do? What exactly is the problem here? Did the UIDs change? Any suggestions please!