OK so I made some changes.
According to the data sheet the capacitors are optional and appear to be only for filtering. But without the caps my regulator didn't work at all the moment the pumps were connected - so obviously these brushless DC pumps mess up the power supply - switching peaks or so? Still hope to egt some idea on what could possibly be the reason for this.
So I connected a 10 µF cap on the input side to smooth it out. The output has capacitors already on the device side - both have 100µF and 100 nF caps. It helped a lot: my devices switched on but one of them had crashed the next morning (i.e. was not responding to http requests). So not stable. The 7805 was pretty hot but not too hot to handle so the heat sink must have been around 50°C, shouldn't be an issue. The 7805 is screwed on tightly with a bit of heat conducting paste in between.
Next: a quick experiment with the caps as suggested in the data sheet (100 nF + 220 nF on the input; 100 nF on the output side - film caps as that's what I have on hand), and also that got the devices to start up. I didn't do stability tests, but went on:
The current configuration: a 12V -> 5V buck converter module. Running for the third day now, so far so good, both devices are stable. So that's a win.
Now if only I could get an idea of what those brushless motors are doing with my power supply I'd be really happy, but it seems I have to wait until I can buy a scope.