Theorem. There is an uncountable graph Γ that is not a Cayley graph in the set-theoretic universe V, but which is a Cayley graph in a larger set-theoretic universe, obtained by forcing.
Theorem. There is an uncountable graph $\Gamma$ that is not a Cayley graph in the set-theoretic universe $V$, but which is a Cayley graph in a larger set-theoretic universe, obtained by forcing.
ProofProof. Let Γ$\Gamma$ be a directed graph that is a tree, such that all vertices have infinite in-out degree, but such that some of these degrees are countable and some uncountable. For example, perhaps all the in-degrees are countable and all out-degrees are uncountable. It is not difficult to construct such a graph. Clearly, Γ$\Gamma$ cannot be a Cayley graph, since the degrees don't match. Denote the (current) set-theoretic universe by V$V$, and perform forcing to a forcing extension V[G]$V[G]$ in which Γ$\Gamma$ is countable. (It is a remarkable fact about forcing that any set at all can become countable in a forcing extension.) In the extension V[G]$V[G]$, the graph Γ$\Gamma$ is the countable tree in which every vertex has countably infinite in-out degree. Thus, in the forcing extension, Γ$\Gamma$ is the Cayley graph of the free group on countably many generators.QED $_\square$
Theorem. There is a graph Γ, which is not a Cayley graph, but every finite subgraph of Γ is part of a Cayley graph. Indeed, every countable subgraph of Γ is part of a Cayley graph. Every countable subgraph of Γ can be extended to a larger countable subgraph of Γ that is a Cayley graph.
Theorem. There is a graph $\Gamma$ which is not a Cayley graph, but every finite subgraph of $\Gamma$ is part of a Cayley graph. Indeed, every countable subgraph of $\Gamma$ is part of a Cayley graph. Every countable subgraph of $\Gamma$ can be extended to a larger countable subgraph of $\Gamma$ that is a Cayley graph.
ProofProof. The same graph Γ$\Gamma$ as above works. Every countable subgraph of Γ$\Gamma$ involves only countably many edges, and can be placed into a countable subgraph of Γ$\Gamma$ that is the Cayley graph of the free group on countably many generators. QED$_\square$
Let me also give the fuller details for the finite-degree case case, following the suggestion of François Dorais (and my tree tree-of-attempts argument).
Theorem. There is a finitistic condition on countable graphs Γ that holds exactly of the finite-degree Cayley graphs. Specifically, the set of finite-degree countable Cayley graphs has complexity at most Σ04 in the arithmetic hierarchy.
Theorem. There is a finitistic condition on countable graphs $\Gamma$ that holds exactly of the finite-degree Cayley graphs. Specifically, the set of finite-degree countable Cayley graphs has complexity at most $\sum_4^0$ in the arithmetic hierarchy.
ProofProof. Let us suppose that the graph Γ$\Gamma$ is given to us simply as a binary relation on ω$\omega$, that is, an element of 2ωxω$2^{\omega\times\omega}$. The assertion that the graph is connected has complexity Π02$\prod_2^0$, since you must only say that every two vertices are connected by a finite path. The assertion that the graph has finite degree and all in-out degrees are the same has complexity Σ04$\sum_4^0$, since you can say "there is a natural number k$k$ such that for all vertices v$v$ there are k$k$ vertices w1,...,wk$w_1,\dotsc,w_k$ pointing at v$v$, such that no other vertex points at v$v$ (and similarly for pointing out).
Now, suppose that Γ$\Gamma$ is a connected directed graph and all in-out degrees are k$k$. Fix a node e$e$ that will represent the group identity (if Γ$\Gamma$ is a Cayley graph, any node will do since they all look the same, so take e=0$e=0$). Let us refer to the k$k$ nodes pointed at from e$e$ as the set of generators (since if Γ$\Gamma$ really is a Cayley graph, these will be the generators). Define that p$p$ is a partial labeling of the edges of Γ$\Gamma$ with generators, if p$p$ is a function defined in a finite distance ball of e$e$ in Γ$\Gamma$, where p$p$ labels each arrow in that ball with a generator. Such a labeling is coherent if first, for every node every generator is used once going out from that node and once going into that node, and second, if for every node v$v$, if there is a loop starting and ending at v$v$, then the word w$w$ obtained from that loop works as a loop from every node to itself. We only enforce the requirements on coherence of p$p$ as far as p$p$ is defined (since it is merely a partial function). Thus, a coherent labeling is an attempt to make a labeling of the the graph into a Cayley graph, that has not run into trouble yet.
Let T$T$ be the collection of finite coherent labelings, labeling all edges on the first n$n$ nodes for some n$n$. This is a finitely branching tree under inclusion.
I claim that Γ$\Gamma$ is a Cayley graph if and only if there are arbitrarily such large coherent labelings. The forward direction is clear, since we may restrict a full coherent labeling to any finite subgraph. Conversely, if we can find a coherent labeling for any finite subgraph of Γ$\Gamma$, then the tree T$T$ is infinite and finitely branching. Thus, by Konig's lemma there is an infinite branch. Such a branch labels all the edges in Γ$\Gamma$ and satisfies the coherence condition. Such a labeling exactly provides a group presentation with Cayley graph Γ$\Gamma$.
The complexity of saying that every initial segment of the nodes admits a coherent labeling is Π02$\prod_2^0$, since you must say for every n$n$, there is a labeling p$p$ of the first n$n$ nodes such that p$p$ is coherent. Being coherent is a Δ00$\Delta_0^0$ requirement on p$p$. QED$_\square$
This still leaves the case of countably many generators wide open. Also, this still doesn't answer the question about having a computable graph Γ$\Gamma$, which is a Cayley graph, but which has no computable presentation. Such an example would be very interesting. Even in the finite degree case, as I mentioned in the question, the best the argument above produces is a low branch.
