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 finite 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.

<strike>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. </strike>