Proof of work systems are generally used where you do not trust the client; the Bitcoin one is used to slow down the generation of new coins and is adaptive; if hardware speeds up, the work gets harder.
By contrast, an exchange has a contractual agreement with the client, and can require it to authenticate, encrypt etc.
The central problem, though, is that exchanges want to be low-latency, which is the opposite of a proof-of-work system.
A more convincing solution to the current problems of HFT is to have a minimum (or fixed) order lifetime; any order is valid for x seconds. Much of the HFT activity involves submitting and cancelling orders very quickly just to test the water and discover information about the order book, or to fool less sophisticated algorithms. By fixing the order lifetime, the orders can actually be filled.
On the other hand, if there was a kind of Bitcoin-style exchange with a public interface, there might be cause for trust-less transactions, but I suspect that would involve escrow of margin, rather than proof of work on the interface.