I've managed to answer a few of the latter questions.
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.
Proof. Let Γ 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, Γ cannot be a Cayley graph, since the degrees don't match. Denote the (current) set-theoretic universe by V, and perform forcing to a forcing extension V[G] in which Γ 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], the graph Γ is the countable tree in which every vertex has countably infinite in-out degree. Thus, in the forcing extension, Γ is the Cayley graph of the free group on countably many generators.QED
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.
Proof. The same graph Γ as above works. Every countable subgraph of Γ involves only countably many edges, and can be placed into a countable subgraph of Γ that is the Cayley graph of the free group on countably many generators. QED
The conclusion is that you cannot tell if an uncountable graph is a Cayley graph by looking only at the finite subgraphs, or indeed, by looking only at its countable subgraphs.
These observations show that in the uncountable case, one should just restrict the question at the outset to graphs satisfying the degree-matching condition.