I would look up a book on the calculus of finite differences in a multivariate setting.
The claim here is to show that for any multi-index $\alpha=(\alpha_1,\ldots,\alpha_n)$
of length $k$ one can express the multiple derivative at zero
$$
\left(\frac{\partial}{\partial t}\right)^\alpha \
(t_1x_1+\cdots+ t_n x_n)^k
$$
as a linear combination of finite difference analogous expressions
which should only involve the evaluation of $(t_1x_1+\cdots+ t_n x_n)^k$
at integer points $(t_1,\ldots,t_n)$ with nonnegative coordinates adding up
to $k$. This is the same as the above candidate basis considered by you and Peter.
I don't know if there exists a multivariate analogue of the Newton series. If so
then this would immediately imply the wanted statement.

Edit:
Apparently there is such a formula due to Lascoux and Schutzenberger, see Theorem 9.6.1 page 148 in the book
"Symmetric functions and combinatorial operators on polynomials" by Alain Lascoux.
Another source on the web is here. It also has the required property here which is that the number of finite differences taken is the same as the degree of the multiplying Schubert polynomial.

Edit: @Jesko you're right it is a bit more complicated than what I said. Also, the Lascoux-Schutzenberger formula might not be the simplest to use here.

First note that expressions
$$
\prod_{i=1}^{n-1} (x_i-x_n)^{\beta_i}\ \times\ (kx_n)^{k-|\beta|}\ ,
$$
where $\beta$ ranges over multiindices with $n-1$ components and length $|\beta|\le k$,
form a basis.
Now you get the latter as derivatives
$$
\left(\frac{\partial}{\partial t}\right)^{\beta} \
\left(t_1x_1+\cdots+ t_{n-1} x_{n-1}+\left(k-\sum_{i=1}^{n-1}t_i\right)x_n\right)^k
$$
at $t=0$.

Call $f(t_1,\ldots,t_{n-1})$ the polynomial function to be hit with derivatives.
One has a multivariate Newton expansion for it:
$$
f(t)=\sum_{m} (t-a)^m \partial^m f(a_{11},a_{21},\ldots,a_{n-1,1})
$$
as follows.
Here $a$ stands for a matrix of indeterminates $(a_{ij})$ with $1\le i\le n-1$
and $1\le j\le d$, with $d$ high enough.
Let $\partial_{ij}$ denote the divided difference operator acting on functions of these indeterminates
as
$$
\partial_{ij} g=\frac{1}{a_{i,j+1}-a_{ij}}\left(
g({\rm argument\ with\ }a_{i,j+1}\ {\rm and}\ a_{ij}\ {\rm exchanged})- g
\right)\ .
$$
The notation $m=(m_1,\ldots,m_{n-1})$ is for a multiindex with nonnegative entries.
We also write the corresponding operator
$$
\partial^m = \prod_{i=1}^{n-1} \left(\partial_{i, m_i}
\cdots\partial_{i,2}\partial_{i,1}\right)
$$
noting that finite difference operators concerning different groups of variables commute.
Finally
$$
(t-a)^m=\prod_{i=1}^{n-1} \left((t_i-a_{i,m_i})\cdots(t_i-a_{i,2})(t_i-a_{i,1})\right)\ .
$$
The formula basically amounts to applying Newton's univariate formula in each coordinate direction separately.
Now use this with the choice $a_{i,j}=j-1$, then take the beta derivative in the $t$'s
and that should be it.