Already restarted the phone twice and then removed the battery after no success. Also cleared all the cache on every app I could with no success.
Turns out the download manager had somehow been disabled (without even knowing it existed) without warning. After enabling it again, the Play Store works again.