But somebody can also do the proof of work from multiple hosts (or parallelized on the same host, e.g. with GPU computation). How does a proof-of-work in this case actually do more than just throttling the server's responses?

Because there’s more work involved.

Okay, but that's kinda like saying eating healthy is good because you get to deprive oneself of donuts: that is, I feel like it's mixing up the cost and benefit. The point of the work is (from what I'm understanding here) to make it less feasible for bots to flood a server with requests, but doing the throttling server-side would have the exact same effect more consistently (i.e. in a way that's not easily evaded by GPU/FPGA/ASIC acceleration and doesn't punish normal users).