Here is a class of examples of infinite hyperbolic groups $G$ such that every self-quasi-isometry $G\to G$ is at finite distance from a left-translation by an element of $G$.
Start with a compact connected $n$-dimensional manifold $M$ with nonempty boundary which admits a hyperbolic metric such that the boundary is totally-geodesic. Then the universal cover $\tilde{M}$ of $M$ is isometric to a certain convex subset $C\subset {\mathbb H}^n$ in the hyperbolic $n$-space, $n\ge 3$. The fundamental group $\pi(M)$ of $M$ acts on $C$ isometrically as the group of covering transformations $\Pi$ for $\tilde{M}\to M$. Let $G$ denote the maximal subgroup of isometries of ${\mathbb H}^n$ preserving $C$. Since $C$ has infinitely many boundary components, the subgroup $G$ is discrete; it acts on $C$ cocompactly since $\Pi< G$. Thus, $G$ is a hyperbolic group. As it turns out, every quasi-isometry $C\to C$ is within finite distance from an element of $G$, see
Frígerio, Roberto, Commensurability of hyperbolic manifolds with geodesic boundary, Geom. Dedicata 118, 105-131 (2006). ZBL1096.32014.
Thus, $G$ satisfies the required property.
As for the original question, the answer is negative even when $G=H$, unless $G$ is finite. I'll prove it only for nonelementary hyperbolic groups $G$. Let $x\in G$ be an element of infinite order and $L_x: G\to G$ be the left translation of $G$ by $x$ ($L_x(y)=xy$). Then $L_x$ is an isometry of $G$. However, $L_x$ does not satisfy (*) for any constant $C$. Indeed, apply $(*)$ with $h=g^{-1}$, then you get
$$
d(gxg^{-1}, 1) = d(xgxg^{-1}, x)=d(xgxg^{-1}, xgg^{-1})\le C
$$
for all $g\in G$. But if $x, g$ do not commute and $g$ has infinite order, then
$$
\lim_{n\to\infty} d(g^nxg^{-n}, 1)=\infty.
$$
As for your "secret question", it sounds very difficult. I am sure it has negative answer (in general) but I do not know how to construct an example.
Let $E$ be compact. Then given $\epsilon>0$ , there exists a finite $\frac{\epsilon}{3}$ net $A=\{f_{1},...,f_{n}\}$ . Now $f_{i}$'s are uniformly continuous (by continuity on a compact metric space)
There exists $\delta_{i}$ s.t $|f_{i}(x)-f_{i}(y)|\leq \frac{\epsilon}{3}$ for all $x,y$ s.t
$d(x,y)<\delta_{i}$ . So take the minimum of all the finitely many $\delta_{i}$ to get that $|f_{i}(x)-f_{i}(y)|<\frac{\epsilon}{3}\,,\forall x,y$ s.t. $d(x,y)<\delta$.
Now for any $f\in E$ . There exists $f_{i}$ such that $\sup_{x\in X}|f(x)-f_{i}(x)|<\frac{\epsilon}{3}$ by construction of the epsilon net. Then If $d(x,y)<\delta$ then,
$$|f(x)-f(y)|\leq |f(x)-f_{i}(x)| + |f_{i}(x)-f_{i}(y)|+|f_{i}(y)-f(y)|<3\cdot\frac{\epsilon}{3}$$ .
And this proves that $E$ is equicontinuous.
To sum it up, Arzela-Ascoli theorem says that a set $E\subset C(K)$ is compact if and only if it is closed,
bounded and equicontinuous.
Best Answer
Here is one:
Theorem. Let $X$ be a proper geodesic $\delta$-hyperbolic space and $f_n: X\to X$ is a sequence of $L$-bilipschitz homeomorphisms such that there exists $x\in X, C\in {\mathbb R}$ satisfying $d(x, f_n(x))\le C$. Then, after extraction, the sequence $$ f_n: \bar{X}\to \bar{X} $$ converges in the uniform topology. Here $\bar{X}=X\cup \partial X$ equipped with the usual topology (and the uniform structure).
A proof is an application of the Morse Lemma and chasing through the definition of the uniform structure on $\bar{X}$. One can prove a similar result by weakening $L$-bilipschitz to $(L,A)$-quasi-isometric, but that requires modifying the notion of convergence on $X$.