2 deleted 6 characters in body

Take $G=\mathbb{Z}$. Then computing $|\operatorname{Hom}(G, H)|=|H|$ is the same as computing the size of a finitely presented group, and is thus wildly undecidable. This eliminates both the general case you seem to ask about, and the case of fundamental groups of surfaces (replacing $\mathbb{Z}$ with, say $\mathbb{Z}\oplus \mathbb{Z}$ and letting your surface $S$ be a torus).

In other words, this problem seems essentially intractable as you've asked it. On the other hand, if you restrict $H$ to lie in the class of finite groups, then the complexity is bounded above by $$|\text{# |H|^{|\text{# of generators of } G|\cdot |H|\cdot G|}\cdot \sum_r t_H(|r|)$$ where the sum is taken over the relations of the given presentation of $G$, and where $t_H(|r|)$ is the time complexity of deciding the word problem in $H$ for a word of length $|r|$. To see this, consider the algorithm which considers all maps $${\text{generators of G}\to H}$$ of which there are $$|\text{# |H|^{|\text{# of generators of } G|\cdot |H|,$$ G|},$$and for each map, checks whether the relations of G are satisfied in H. This algorithm has the time complexity described. So essentially your question is identical to finding the time complexity of solving the word problem in whatever class of groups H belongs to, about which there is tons of literature. 1 Take G=\mathbb{Z}. Then computing |\operatorname{Hom}(G, H)|=|H| is the same as computing the size of a finitely presented group, and is thus wildly undecidable. This eliminates both the general case you seem to ask about, and the case of fundamental groups of surfaces (replacing \mathbb{Z} with, say \mathbb{Z}\oplus \mathbb{Z} and letting your surface S be a torus). In other words, this problem seems essentially intractable as you've asked it. On the other hand, if you restrict H to lie in the class of finite groups, then the complexity is bounded above by$$|\text{# of generators of } G|\cdot |H|\cdot \sum_r t_H(|r|)$$where the sum is taken over the relations of the given presentation of G, and where t_H(|r|) is the time complexity of deciding the word problem in H for a word of length |r|. To see this, consider the algorithm which considers all maps$${\text{generators of $G$}\to H}$$of which there are$$|\text{# of generators of } G|\cdot |H|, and for each map, checks whether the relations of $G$ are satisfied in $H$. This algorithm has the time complexity described.

So essentially your question is identical to finding the time complexity of solving the word problem in whatever class of groups $H$ belongs to, about which there is tons of literature.