I get a slightly different formula:
$$\sum_{V} \frac{d(V)^{2g-2-n}}{|G|^{2g-2}} \prod_{i=1}^n |k_i|\chi_V(k_i)$$
Here $|k_i|$ denotes the size of the conjugacy class.
I prefer to express this in a slightly different way. For a conjugacy class $k$ and irreducible representation $V$ of $G$, let $f^V_k$ denote the scalar by which the indicator function $k \in Z(\mathbb C[G])$ acts on $V$. In these terms the formula is:
$$\sum_V \left(\frac{d(V)}{|G|}\right)^{2g-2} \prod_{i=1}^n f^V_{k_i}$$
To obtain the first formula from the second, note that the numbers $f^V_k$ are related to characters as follows:
$$f^V_k = \frac{|k|}{d(V)} \chi_V(k)$$
For me, these formulas come from general properties of commutative Frobenius algebras, or equivalently 2d topological field theory (TFT). Namely, given a commutative Frobenius algebra $A$, a genus $g$, and a collection of elements $k_1, \ldots , k_n$ one obtains a number
$$Z_A(g; k_1, \ldots , k_n)$$
recording the value of the TFT on an oriented surface of genus $g$ with $n$ punctures labelled by the elements $k_1, \ldots , k_n$. You can compute this number by first multiplying together the elements $k_1 \ldots k_n$ in $A$, then applying a sequence of $g$ comultipication followed by multiplication operations, finally followed by the Frobenius trace (see cartoon below).
In the case when $A$ is semisimple, one can be more explicit and write everything in terms of a basis of orthogonal idempotents.
In our case we take $A=Z(\mathbb C[G])$, the center of the group algebra, equipped with the trace $t$ (which takes the value $1/|G|$ at the identity element of $G$ and zero on all other elements). The numbers $f^V_k$ is just the change of basis matrix between the conjugacy classes $k$ and the orthogonal idempotents $e_V$ labelled by irreps.
I can't think of a reference for this right now. In this paper I explain some of this stuff in a related context, see e.g. Prop 2.13.