This is *not* an answer, but rather an attempt at working out the $m=\infty$ case properly.

Let's assume we want to know the number of words of length $2N$ ($g_{i_1}\ldots g_{i_{2N}}$) that reduce to the identity, and let's call this quantity $E_{2N}$.
Let's break into two cases: $i_1 = i_{2N}$ and $i_1 \neq i_{2N}$. Obviously the first case contributes $kE_{2N-2}$. In the second case, there must be some index $2p$ such that $i_{2p} = i_1$ and the initial subword $g_{i_1}\ldots g_{i_{2p}} = e = g_{i_{2p+1}} \ldots g_{i_{2N}}$. This would give us a contribution of $kE_{2p-2} * (k-1)/k E_{2N-2p}$ (from the requirement that $i_{2N} \neq i_1$). Except that we've overcounted these words -- there could be multiple indices $p$ that qualify.

Fortunately, we can use simple inclusion-exclusion to get the correct count. These words look like $g_{i_1}\ldots g_{i_{2p_1-1}} g_{i_1} g_{i_{2p_1+1}} \ldots g_{i_{2p_n -1}} g_{i_1} g_{i_{2p_n +1}} \ldots g_{i_{2N}}$, with each subword $g_{i_{2p_j+1}} \ldots g_{i_{2p_{j+1}-1}} g_{i_1}$ equal to the identity. We get a count $kE_{2p_1 - 2} * (1/k E_{2p_2 - 2p_1}) * \ldots * (1/k E_{2p_n - 2p_{n-1}}) * ((k-1)/k E_{2N-2p_n}$. Each factor of $1/k$ comes from the requirement that the terminal end of the subword is $i_1$; the factor of $(k-1)/k$ comes from the fact that $i_{2N} \neq i_1$, and the initial factor of $k$ comes from summing over possible values of $i_1$.

So we have the following recursion:
\begin{equation}
E_{2N} = kE_{2N-2} + \sum_{p=1}^{N-1} (k-1) E_{2p-2} E_{2N-2p} - \sum_{0<p_1<p_2<N} (k-1)/k E_{2p_1 -2} E_{2p_2 -2p_1} E_{2N-2p_2} + \ldots
\end{equation}
Writing this as a generating function equation, we get:
\begin{equation}
E(x) = \sum_n E_{2n} x^n
\end{equation}
\begin{equation}
E(x) = 1 + kxE(x) + (k-1)x E(x)(E(x)-1) - \frac{k-1}{k} x E(x)(E(x)-1)^2 + \frac{k-1}{k^2} x E(x)(E(x)-1)^3 -\ldots
\end{equation}
or
\begin{equation}
E(x) = 1 + xE(x) * [k + (k-1) (E(x)-1) / (1 + (E(x)-1)/k)] \,.
\end{equation}
The extra $1$ term at the beginning is to account for $E_0$, and the $(E(x)-1)$ terms are to account for the fact that the subwords cannot be 0-length. Multiplying both sides by $k-1+E$ we get
\begin{equation}
0 = (k-1) - (k-2)E(x) + (k^2x -1) E(x)^2
\end{equation}
or
\begin{equation}
E(x) = \frac{k \sqrt{1-4(k-1)x} - (k-2)}{2(1-k^2x)} \,.
\end{equation}
I would greatly appreciate it if people were to check my math.

allpairs $g_i g_j$ to have order 3? Probably you meant justsomepairs, and then, of course, the answer will have to be phrased in terms of the associated graph (but I don't know what it will look like in terms of that). I only mean to emphasise that this is actually a huge family of questions. $\endgroup$ – LSpice Apr 10 at 18:28allpairs have order 3, and the Coxeter diagram is a simplex. $\endgroup$ – Craig Apr 10 at 18:35