Neat! This does seem like it should work!

Semantic quibble: it's less "proof of work" and more "proof of hardware+work". Or, as they call it, hardware-bound proof of work. The reason you can't offload the challenge to a more powerful device is that they rely on identifying stable differences for each device class that ultimately trace down to the hardware they're running on.

From reading the abstract, isn't this just exploiting the same class of security vulnerabilities that the OP is lamenting are being fixed?

Not sure. Maybe not, if it's about device-specific information instead of headed-vs-headless distinctions?

Can privacy be preserved with zero knowledge proofs? I don't like the idea of universal fingerprinted devices in an already heavily authoritarian world.