In the general case, I want to say that determining $|Hom(G,H)|$ is incomputable, arguing that you could use the number to test for simplicity of a presentation, but I am new to this area and I keep finding flaws with my argument.

While I believe the general case is incomputable, there are computable special cases. One in particular that interests me is: compute $|Hom(\pi(S),G)|$ for the fundamental group of a surface $S$, given by a triangulation, and $G$ finite. This arises in Mednykh’s Formula for a 2D TLFT invariant ( $|G|^{\chi(S)-1}|Hom(\pi(S),G)|$), which one can approximate (details in a paper to appear by Gorjan Alagic and myself) efficiently on a quantum computer. However, I have been unable to find any information on the classical complexity of finding $|Hom(\pi(S),G)|$ (with $\pi(S),G$ given in any way) to contrast with the quantum case, or even a discussion of when $|Hom(G,H)|$ is computable and what the complexity of computing it should be.

So, that leaves me with the possibly too broad:

When is $|Hom(G,H)|$ computable for finitely presented $G,H$ and in these special cases what is the classical complexity of computing it?