Can you log in normally from the login screen? Is it only an issue with 'startx'?

No, if I try to boot directly to GUI the resolution changes several times (I can see that via VNC which is available at boot time for the VPS because the VNC size is changing several times) and then get's stuck. This happens on two different VPS. I have upgraded from 18.04 LTS. But this error is not connected to the update. I also tried to use a fresh install and the result was the same. Which means there is no login screen on both machines.

If it get's stuck the beavior is different on both VPS even if I copy everything except /sys /run /proc (which means the same installation is used) one VPS gets stuck in a purple screen and it is possible to change to command line via Alt+F. The other one ends up in a blueish screen with lines and a blinking cursor but this one is totally stuck. I added two screenshots of that.

Sometimes I see the desktop for a part of a socond between the resolution changes. I also tried to set a fixed resolution but was not sucessfull because the switching is still happening. If I stop the gdm serrvice startx with root is possible afterwards. IT took me a while to realize this because at first I thought I should focus on the GUI boot problem.

I now switched both VPS to multi user target insted of graphical boot. If I use stop service gdm3 and start service gdm3 the result is the same like described above. XRDP combined with remote desktop is also only working via root login.

Also please run:
  ls -l /usr/libexec/gnome-session-binary
ls -l /usr/libexec/gnome-session-binary
-rwxr-xr-x 1 root root 334664 Mar 26 13:22 /usr/libexec/gnome-session-binary

On tests with xrdp I also saw some other errors in syslog which are more detailed as the gnome session permission error which does not seem to be the root cause:
May 27 18:34:59 systemd[587724]: at-spi-dbus-bus.service: Failed to execute command: Permission denied
May 27 18:34:59 systemd[587724]: at-spi-dbus-bus.service: Failed at step EXEC spawning /usr/libexec/at-spi-bus-launcher: Permission denied
May 27 18:34:59 systemd[1678]: at-spi-dbus-bus.service: Main process exited, code=exited, status=203/EXEC

I have seen some oher useers with this kind of problem which switched off at-spi-dbus-bus.service. I tried that and ended up with. That's where I stopped trying and switched at-spi-dbus-bus.service to start agein like before. Which means I'm now on standard settings after upgrade again:

dbus-daemon[642845]: [session uid=0 pid=642843] Activating service name='org.freedesktop.systemd1' requested by ':1.20' (uid=0 pid=642800 comm="/usr/libexec/gnome-session-binary --builtin " label="unconfined")
May 27 19:49:30 dbus-daemon[642845]: [session uid=0 pid=642843] Activated service 'org.freedesktop.systemd1' failed: Process org.freedesktop.systemd1 exited with status 1
May 27 19:49:30 org.gtk.vfs.Daemon[642897]: A connection to the bus can't be made
May 27 19:49:30 gnome-control-c[646635]: gnome-control-center-search-provider: Fatal IO error 11 (Die Ressource ist zur Zeit nicht verfügbar) on X server :0.
May 27 19:49:30 seahorse[643522]: seahorse: Fatal IO error 11 (Die Ressource ist zur Zeit nicht verfügbar) on X server :0.
May 27 19:49:30 org.gnome.Chara[646649]: org.gnome.Characters.BackgroundService: Fatal IO error 11 (Die Ressource ist zur Zeit nicht verfügbar) on X server :0.
May 27 19:49:30 gnome-calendar[643523]: gnome-calendar: Fatal IO error 11 (Die Ressource ist zur Zeit nicht verfügbar) on X server :0.
May 27 19:49:30 systemd[1]: root-.cache-gvfs.mount: Succeeded.
May 27 19:49:30 systemd[225333]: root-.cache-gvfs.mount: Succeeded.
May 27 19:49:30 org.gnome.Shell.CalendarServer[643029]: gnome-shell-calendar-server[643029]: Lost (or failed to acquire) the name org.gnome.Shell.CalendarServer - exiting
May 27 19:49:30 systemd[1678]: root-.cache-gvfs.mount: Succeeded.
May 27 19:49:30 systemd[1679]: root-.cache-gvfs.mount: Succeeded.
May 27 19:49:30 org.gtk.vfs.Daemon[643591]: A connection to the bus can't be made
May 27 19:49:30 org.gtk.vfs.Daemon[643694]: A connection to the bus can't be made