Why is my iMac (late 2013) HDD so slow?
To finish this question: I had opened a bug report with Apple. They determined that a botched Aperture photo library migration lead to excessive disk I/O. In the end, I reformatted the whole Mac. Plus to make the machine more useable, I attached a 256 GB Thunderbolt SSD and created a FusionDrive, as per this blog (in german). There are lots of howtos explaining how to create a FusionDrive. This really gave the machine an incredible performance boost.