In my paper

The uniform word problem for groups and finite Rees quotients of E-unitary inverse semigroups, Journal of Algebra, Volume 266, Number 1, 1 August 2003 , pp. 1-13(13)

I prove that it is undecidable whether a directed labeled graph has a label preserving-embedding into the Cayley graph of a finite group.  More generally, if V is a class of groups closed under finite direct products, subgroups and homomorphic images, then the embeddability of a finite labeled graph into the Cayley graph of a group in V is equivalent to the uniform word problem for V.

If the graph is unlabeled one can try all the finitely many labelings over an alphabet of size the number of edges in the graph. So the second problem is undecidable.