This question is pretty old but I had the exact same problem with the exact same distro so I'll answer with how I solved it after uninstalling protonvpn.
By running

nmcli device

I found out I had two extra connections that had remained there and the system was trying to route through them, so after identifying them I simply did

sudo nmcli connection delete pvpn-killswitch

sudo nmcli connection delete pvpn-ipv6leak-protection

After that rebooting solved everything.

Also, note that there is also a workaround to use protonvpn service if after the installation internet stopped working. Simply run:

nmcli connection show --active

Then,

nmcli connection delete [connection name]

In my case the code was:

nmcli connection delete pvpn-ipv6leak-protection

After that, just open protonvpn and connect normally.