Characters of permutation groups

This follows from using generating functions a la Polya. By the cycle index formula, one sees that (using the notation of $C_n(k,j)$ for permutations in $S_n$ with $k$ cycles including $j$ fixed points) $$ \sum_{n=0}^{\infty} \frac{t^n}{n!} \sum_{k,j} C_n(k,j) y^j x^k = \exp\Big( tx y +\sum_{j=2}^{\infty} \frac{x t^j}{j}\Big). \tag{1} $$ Since $\sum_{j=1}^{\infty} t^j/j = -\log (1-t)$, we may write the above as $$ (1-t)^{-x}\exp(tx(y-1)). \tag{2} $$

If we take here $y=1$ and compare coefficients of $t^n$ we obtain the formula you noted: $$ \frac{1}{n!} \sum_{k, j} C_n(k,j) x^k = (-1)^n\binom{-x}{n}= \frac{x(x+1)(x+2)\cdots (x+n-1)}{n!}. \tag{3} $$ Next, differentiating (1) and (2) with respect to $y$ and then setting $y=1$ gives $$ \sum_{n=0}^{\infty} \frac{t^n}{n!} \sum_{k,j} j C_n(k,j) x^k = tx (1-t)^{-x}. $$ Comparing coefficients of $t^n$ here gives $$ \frac{1}{n!} \sum_{k, j} j C_n(k,j) x^k = (-1)^{n-1}x\binom{-x}{n-1}=x\frac{x(x+1)\cdots (x+n-2)}{(n-1)!}. \tag{4} $$ Combining (3) and (4) gives your formula.

For the reasons apparent below I shall use the notation $C_N(m,j)$, not $C(m,j)$. It is sufficient to prove $$ \sum_{m=0}^N\sum_{j=0}^m jC_N(m,j)x^m=Nx\cdot x(x+1)\cdots (x+N-2), $$ as this formula together with your first formula implies what you want to prove. The LHS of this is the same as $$ \sum_{(\sigma,k)\colon \sigma\in S_N \text{ has } m \text{ cycles}, \,\sigma(k)=k }x^m, $$ which, after changing the order of summation and denoting $m'=m-1$, is the same as $$ \sum_{k=1}^N x\sum_{m'=0}^{N-1}\sum_{j=0}^{m'}C_{N-1}(m',j)x^{m'}=\sum_{k=1}^Nx\cdot x(x+1)\cdots(x+N-2), $$ which is equal to $Nx\cdot x(x+1)\cdots(x+N-2)$, as required.