If G is infinite cyclic and g generates G, then the answer is: "yes, there is such a map" (so in particular, it's not undecidable at all).
So I'm not quite sure what the original poster meant by saying that if G is cyclic, the problem is redicible to the word problem. Maybe, if someone sees how that argument would go (and what the right hypothesis is), they could explain it.
Then it might be more clear whether this same argument can be applied if G is not cyclic.
Charles is right, of course, to say that a map from G to H restricts to a map from the cyclic group generated by g, to H, but if you could determine that there was no appropriate map from G to H, that wouldn't necessarily tell you that there was no appropriate map from < g> to H, so, on the face of it, it's possible that it could be decidable that there were no appropriate maps from G to H, but not decidable whether or not there were appropriate maps from < g> to H. (Here, "appropriate" means "taking g to h".)
(Edited to correct html issue.)