Consider the following simplified example of the same phenomenon, which many students find clarifying.
Let $f(n)=1$, if there are $n$ consecutive $7$s in the decimal expansion of $\pi$, and otherwise $f(n)=0$. Is this function computable?
A naive attempt to compute $f(n)$ would simply proceed to search $\pi$ for $n$ consecutive $7$s. If found, the algorithm outputs $1$, but otherwise....and then the naive algorithm doesn't seem to know when to output $0$, and so students sometimes expect that $f$ is not computable.
But actually, $f$ is a computable function. If it happens that there are arbitrarily long sequences of $7$s in the decimal expansion of $\pi$, an open question, then $f$ is the constant $1$ function, which is certainly computable. Otherwise, there is some longest sequence of $7$s in $\pi$, having length $N$, and so $f$ is the function that is $1$ up to $N$ and then $0$ above $N$. And this function also is computable, for any particular $N$.
So the situation is that we have proved that $f$ is computable by exhibiting several algorithms, and proving that $f$ is definitely computed by one of them, but we don't know which one. (In fact, $f$ is linear time computable.) So we have proved that $f$ is a computable function, but by a pure existence proof that merely shows there is an algorithm computing $f$, without explicitly exhibiting it.
It seems to be the same phenomenon in your case, where you have a computable function, but you don't know which algorithm computes it.
Addition. Let me try to address Thierry Zell's concern about the
third question. To my way of thinking, the phenomenon of
the question is an instance of the problem of uniformity
of algorithms, a pervasively considered issue in
computability theory.
To illustrate, consider the question of whether a given
program $p$ halts on input $0$ before another program $q$.
Let $f_p(q)=1$ if it does and otherwise $f_p(q)=0$. Every
such function $f_p$ is computable, for similar reasons to
my $\pi$ function $f$ above, since either $p$ doesn't halt
at all on input $0$, in which case $f_p$ is identically
$0$, or $p$ does halt in $N$ steps, in which case we need
only run $q$ for $N$ steps to see if it halts, and give our
output for $f_p(q)$ by that time. So each $f_p$ is a
computable function. But the joint function
$f(p,q)=f_p(q)$, a binary function, is not computable (if
it were, then we could solve the halting problem: to decide
if $p$ halts on input $0$, design a program $q$ that would
take one step extra after a halt, and ask if $p$ halts
before $q$).
In other words, the function $f(p,q)$ is computable for any
fixed $p$, but not uniformly in $p$. And such uniformity
issues are ubiquitous in computability theory.
In the example of the question, each class of graphs is
decidable, but not uniformly so, since by Tony's answer
there is no uniform algorithm, given a description of the
class, to find the collection of excluded minors. But for
any such fixed class, the membership question is decidable.
The issue of whether a given algorithm is uniform in a
given parameter is a very common concern in computability
theory, and occurs throughout the subject.
This is not a full answer, but perhaps too long for a comment.
Your question is about the distance problem in a fixed Cayley graph. If one also considers the Cayley graph as part of the input then some things are known. This makes sense in the context of permutation groups, where we can explicitly give the generators in a succinct way.
Even and Goldreich in the paper "Minimum-Length Generator Sequence Problem is NP-Hard" (J. ALGORITHMS. Vol. 2, no. 3, pp. 311-313. 1981) showed:
We examine the following questions:
(1) Given a set of generators of a
permutation group G and a target
permutation P, find (the length of) a
shortest generator sequence realizing
P. (2) Given a set of generators of a
permutation group G, find the minimum
upper bound on the length of generator
sequences needed to realize any
permutation in G. We show that both
problems are NP-Hard by reducing the
3XC problem to each of them. The
reductions we use show that these
results hold even if the given set of
generators is restricted to contain
for each generator its inverse, too.
This actually makes the problem NP-Complete (when the length is written in unary).
In other work, Mark Jerrum in "The complexity of finding minimum-length generator sequences" (Theoretical Computer Science Volume 36, 1985, Pages 265-289) showed:
The computational complexity of the
following problem is investigated:
Given a permutation group specified as
a set of generators, and a single
target permutation which is a member
of the group, what is the shortest
expression for the target permutation
in terms of the generators? The
general problem is demonstrated to be
Image -complete and, indeed,is shown
to remain so even when the generator
set is restricted to contain only two
permutations. The restriction on
generator set cardinality is the best
possible, as the problem becomes
soluble in polynomial time if the
generator set contains only one
permutation. An interesting feature of
this problem is that it does not fall
under the headings of ‘two person
games’ or ‘formal languages’ which
cover the great majority of known
Image -complete problems. Some
restricted versions of the problem, in
which the generator set is fixed
rather than being part of the problem
instance, are also investigated and
shown to be computationally tractable.
One result of this kind is that
determining the most compact
expression of a permutation in terms
of ‘cyclicly adjacent transpositions’
can be achieved in polynomial time.
Thus, from an initial arrangement of
distinct objects on a circle, one can
quickly compute the smallest number of
interchanges of adjacent objects
required to realise any other
arrangement. Surprisingly, this
problem appears substantially more
difficult to solve than the related
one (for which a solution has been
known for some time) in which the
objects are arranged on a line
segment.
Note that Jerrum considers the length of the path in binary, which changes things.
Best Answer
The short answer is that there are no implications.
As Scott Aaronson said on his blog, the fact that even a polynomial time algorithm for GI has no implications for complexity classes is one reason some people conjectured that GI might be in P. He continued:
Similarly there are no implications for quantum computing.
As for the prospects for further improvement, the best reference as of this writing may be Jeremy Kun's notes on Babai's talk. One key point is that Babai's algorithm relies on a strategy that he calls "split or Johnson" and he can show that this strategy is not enough to put GI in P.
UPDATE: Babai has posted a preprint to the ArXiv.
UPDATE: Babai's talk at the Institute for Advanced Study is available online. IMO this talk is much better than the very first talk he gave at Chicago; he's had time to prepare slides and greatly clarify the presentation.