On 1: That's exactly the point of this paper. That's what the EMH claims, and what this paper is linking to P=NP. If this paper is correct then markets are not violations of P=NP, and a lot of economists are wrong (or P=NP).

On 2: My answer to both problems (any problems) is Turing equivalence. If one algorithm of people and computers can solve the problem, then so can another one with the same resources. And given our knowledge of how different optimization algorithms can give results biased in different ways, it should be possible to find an algorithm that biases better towards equality than our current one.

But again that's a theoretical justification, which is why it's an interesting avenue of further research. I don't have any concrete answers because that would require research on the problem I haven't (and don't have the resources to) conduct(ed). And to make it quite clear, it's entirely possible the answer of this research could be markets are always the best (which would be disappointing, but possible), but it seems more likely that we would discover some new systems.

Edit: The economic calculation problem is the EMH rephrased (which this paper is making clear is a valid criticism only if P=NP). So that problem in specific is invalidated by this paper.

Edit 2: The principle agent problem is solved by the "equal number of people" component. And the fact that markets often involve selling other people's resources through their governments and other representatives anyway (see Saudi Arabia selling oil to enrich only their leaders on our open markets; while they use slaves), so it's not like markets are somehow a perfect solution to this problem as they currently stand.