There are already two posts mentioning a kernel (6.1.159-1) related authentication problem!
(beside my own one with kernel 5.15)
and
Those posts gave me actually the idea to switch the kernel which solved the problem. In summery, the polkit problem seems not only be related to the permissions and reboot, but to certain kernels as well.