Value of Vandermonde type determinant

Sure, at least you can find such a formula for any fixed $k \geqslant n$. Not sure about a general formula for an unknown $k$ though.

Here is a hint: if all the $x_i$ are distinct, vector $(x_1^k,\ldots,x_n^k)$ is a linear combination of vectors $(x_1^i,\ldots,x_n^i)$, $i=0,\,1,\ldots,n-1$. If $$ (x_1^k,\ldots,x_n^k) = \sum_{i=0}^{n-1} \lambda_i (x_1^i,\ldots,x_n^i), $$ then your determinant is simply equal to $\lambda_{n-1}$ times the usual Vandermonde determinant. So all you need to do is find $\lambda_{n-1}$.

To continue Dan's answer, we want $$ x_i^k = \sum_{j=0}^{n-1} \lambda_j x_i^j, \qquad 1 \le i \le n $$ That is the polynomial $p(x) := \sum_{j=0}^{n-1} \lambda_j x^j$ interpolates $x^k$ at $x_0, \ldots, x_{n-1}$. Lagrange interpolation gives $$ p(x) = \sum_{j=0}^{n-1} x_j^k \cdot \prod_{\ell \ne j} \frac{x-x_\ell}{x_j - x_\ell} $$ $\lambda_{n-1}$ is the coefficient of $x^{n-1}$, so it is $$ \lambda_{n-1} = \sum_{j=0}^{n-1} x_j^k \prod_{\ell\ne j} \frac 1{x_j - x_\ell}. $$

Perform Laplace expansion along the last column. As the deletion of the $\ell$-th row and the last column gives a $(n-1)\times(n-1)$ Vandermonde matrix (in the original flavour), we get $$ \sum_{\ell=1}^n (-1)^{\ell+n} x_\ell^k\prod_{i<j\,\textrm{ and }\,i,j\not=\ell}(x_j-x_i). $$