Edit: “Updating to the legacy 580xx drivers doesn’t show me a desktop anymore”, just in case someone else can stumble upon this by searching something similar.

Thanks to @[email protected] and @[email protected] I did try fixing it out of curiosity. I had forgotten to install linux-headers. Hopefully someone who actually has the same problem as me, and needs to fix it, can use the tips given in the comments. On my end, I just had to install linux-headers and one reboot later it worked.

Always check if you have all needed packages and don’t just “remember” that you had them installed.