Finally found the reason why pkexec was broken on my laptop. I had hidepid=2 set for /proc in /etc/fstab. This hides all processes that do not belong to you. Problem is, systemd does not support it.
So, errors are very uninformative, like this:
- GDBus.Error:org.freedesktop.PolicyKit1.Error.Failed: No session for cookie
- polkit-gnome-1-WARNING **: Unable to determine the session we are in
Solutions for this always point in the direction of session registration (pam_loginuid, or pam_systemd), or missing packages. But the fact that /proc needs to be world readable is (almost) nowhere to be found. So, that's why this post.