I figured out this order on $\omega^2$: elements of different columns are ordered by their column number; within column $m$, the order is $0 \gt 1 \gt 2 \gt \cdots \gt n$, where $n$ is the first such that $P(m,n)$ is true; then $0 \lt n+1 \lt n+2 \lt \cdots$. The column is an infinite descending sequence if there is no such $n$. This order is well-founded iff for all $m$ there is an $n$ such that $P(m,n)$ is true.
So I can reduce any $\Pi_{2}^{0}$ sentence to a computable ordering which is well-founded iff the sentence is true. I don't see how to do this for $\Sigma_{2}^{0}$.
Now Wikipedia tells me Kleene's $O$ is $\Pi_{1}^{1}$ complete, so I'm still a long way away from what I should be able to do. Rather than being told what the full reduction is, if instead I could just get a hint for the $\Sigma_{2}^{0}$ case, then maybe I can pretend to myself that I figured "most" of it out on my own?