There's a more general consideration from the theory of Burnside groups and the restricted Burnside problem. The free Burnside group $B(m,n)$ is a quotient of a free $m$-generator group by the subgroup generated by $n$th powers, and $B_0(m,n)$ is the quotient by the subgroup which is the intersection of all finite-index subgroups. Zelmanov proved that $B_0(m,n)$ is finite, resolving the restricted Burnside problem. So if $G$ has a presentation with $m$ generators $F_m\to G$, and $|H|=n$, then any homomorphism $G\to H$ will factor through a homomorphism $F_m \to B_0(m,n) \to H$.
Now, if we assume that $m$ is fixed, and that we have computed $B_0(m,n)$, then for relators $r_1,\ldots, r_k \in F_m$ in a presentation of $G$, we ought to be able to find equivalent relations in $F_m$ of bounded length, and which map to the same element of $B_0(m,n)$. This should be easily computable in polynomial time (given a multiplication table for $B_0(m,n)$), and therefore we may replace the $r_i$ with finitely many elements in the free group. So we precompute all homomorphisms from $B_0(m,n)$ to $H$ which kill a finite collection of elements in $B_0(m,n)$, giving a polynomial-time algorithm to compute the number of homomorphisms. So this answers your question in the affirmative for groups given by a finite presentation of bounded rank.