I skimmed it quickly too, but I think you've misread. The "interesting" claim isn't the 3-SAT encoding; it's earlier where he claims that markets "naturally" have to solve NP-hard problems, in particular that to optimize an investment strategy you have to solve the Knapsack problem. (?!) It's hand-waving nonsense.
It doesn't matter. When people say efficient market, they mean that the market knows whatever is knowable by the present time using current technologies. They don't mean that the market knows everything that's theoretically knowable using unknown/impossible algorithms.
Before there were computers in an efficient market (supposing one exists), the current prices would reflect everything that is known and can be computed/deduced without computers by the present time.
Anyway, the paper misunderstands "known" to mean "anything which can theoretically be known", which obviously includes solutions NP-hard problems. It's just that nobody claims that's what efficient markets are.
I'm surprised he decided to use 3-SAT instead of pointing out the non-convexities which arise in optimization for many interesting markets. Or the problem with digital goods say. That these are exploitable is what leads to excess returns and monopolies. These are failings due to reasons one can argue with computational compexity (non convex optimization is in NP).
The issue with digital goods is also the matter of uncertainty, the issue to do with scarcity or lack thereof and the trickiness of information as a good itself. In essense there is a built in inefficiency for information goods. But the points you bring up are correct and extend beyond digital goods.
