Mainly, my question is in the title, but let me be more precise here.
Let $G$ be a finitely presented group with solvable word problem. If G is not left-orderable, is there an finite-time algorithm to establish this fact?
If the answer to the above question is unknown, is it known in the case $G$ is the fundamental group of a 3-manifold? Or is there a class of groups where it is known?
This is a very nice question, which I don't know how to answer. But I hope the following (shameless self-promotion) will be of interest.
You seem to be looking for some sort of local condition that certifies the (non-)existence of an ordering. Lars Louder and I made the following definition, which seems to encapsulate a certain simple class of orders in a finite amount of data.
Definition: Consider a finite, 2-dimensional cell complex $X$ given by the following data: a finite disjoint union of circles $\mathbb{S}$ and an immersion to a finite graph $$ \partial:\mathbb{S}\to\Gamma ~. $$ [Hopefully it's clear that $\Gamma$ is the 1-skeleton of $X$ and $\partial$ is the coproduct of the attaching maps of the 2-cells.] A stacking of $\partial$ is an embedding $\hat{\partial}:\mathbb{S}\to\Gamma\times\mathbb{R}$ so that $\pi\circ\hat{\partial}=\partial$ (ie $\hat{\partial}$ is a lift of $\partial$).
A point $x$ of $\mathbb{S}$ is called upper if, whenever $\partial(x)=\partial(y)$, the $\mathbb{R}$-coordinate of $\hat{\partial}(x)$ is greater than the $\mathbb{R}$-coordinate of $\hat{\partial}(y)$. Lower points are defined similarly.
The stacking $\hat{\partial}$ is called good if every component of $\mathbb{S}$ contains at least one upper point and at least one lower point.
It's easy to see that the existence of a stacking is equivalent to an order on a certain finite subset of the group; so in particular, if $\pi_1X$ is orderable then a stacking exists. More interestingly, goodness enables a kind of converse.
Proposition: If $X$ admits a good stacking then $\pi_1X$ is left-orderable.
More precisely, you can deduce from our results that, if $X$ has a good stacking, then $\pi_1X$ is locally indicable, and it then follows that $\pi_1X$ is orderable by the Burns--Hale theorem. (It would be nice to have a more direct proof of this fact!)
Note that a good stacking can be found algorithmically. In particular, this provides the kind of "local certificiation" of orderability that I think is relevant to the question.
The following can also be deduced from our results.
Proposition: A finitely presented subgroup $H$ of a one-relator group has a presentation complex with a good stacking if and only if $H$ is torsion-free.
So this provides a class of examples (with solvable word problem) in which orderability can be algorithmically determined.
I would tentatively conjecture that there are other classes of examples that good stackings can also certify in this way. For instance, it's possible that the fundamental group of any compact, irreducible 3-manifold with boundary admits a presentation complex with a good stacking.
Unfortunately, there's no chance of applying this to closed 3-manifolds, since 2-complexes with good stackings are automatically aspherical. But perhaps there's some modification that works?
