TL;DR: The issue is with the Random Track Progression feature of amarok (Hence QRandom). This being enabled is stored in the config, meaning it gets loaded as soon as you start amarok.
Thank you for the suggestion, but even with this I still get the same error.
Now the only packages that are not from Main Repository (OSS) or Main Repository (NON-OSS) are marked as @System: https://paste.opensuse.org/pastes/c88f69764a9c (66 in total).
zypper verify still only complains about mattermost-desktop.
Following step 3 and 4 (reenabling packman) also does not help.
(I should add that throughout all of this I rebooted after every zypper dup --allow-vendor-change, just to be sure that everything is up to date.)
I suppose that I can say with some confidence, that my package situation is not the culprit here.
While typing this I thought about what else might be causing the issue. Some configuration came to mind. I went to look at the amarok configuration file and discovered that next to amarokrc there was an amarokrc.MNwUDu in ~/.config. Deleting both of those resulted in amarok starting again.
Some more experimentation reveals that setting the playback to random order (in the bottom right, Track progression → Random Tracks) causes amarok to immediately crash. As I typically use random track progression amarok stored this in it’s configuration, which was last edited on 2023-03-28T19:02:00Z. After that some update must have broken this feature.
You can try using Random Track Progression, but I would recommend making a backup of your `~/.config/amarokrc, even though amarok crashes before being able to overwrite the config.
Thank you all for your efforts. I suppose I will open a bug on the kde bug tracker after all.