For convenience consider the representation $Y=V_n\oplus V_{n-1,1}$ instead of $V_{n-1,1}$. Then the multiplicity of the representation of $S_n$ indexed by the partition $\lambda$ of $n$ in the $k$th tensor power of $Y$ equals the scalar product of the symmetric function $s_1^k$ (where $s_1=x_1+x_2+\cdots$ denotes a Schur function) with the plethysm $s_\lambda[1+h_1+h_2+h_3+\cdots]$, where $h_i$ is the complete symmetric function of degree $i$. This follows from the theory of inner plethysm; see Exercise 7.74 of Enumerative Combinatorics, volume 2. Since plethysm is in general intractable, I don't expect anything much simpler. This result does allow, however, these decompositions to be computed using Stembridge's Maple package SF for small values of $n$ and $k$.
Addendum. I used the method of Exercise 7.74 to get the analogous result for $V_{n-1,1}$. Namely, the multiplicity of the representation of $S_n$ indexed by the partition $\lambda$ of $n$ in the $k$th tensor power of $V_{n-1,1}$ equals the scalar product of $s_1^k$ with the symmetric function $(1-e_1+e_2-e_3+\cdots)\cdot s_\lambda[1+h_1+h_2+h_3+\cdots]$, where $e_i$ is an elementary symmetric function.
Addendum #2. A alternative formulation is the following. The multiplicity of the representation of $S_n$ indexed by the partition $\lambda$ of $n$ in the $k$th tensor power of $V_{n-1,1}$ equals the scalar product of $(s_1-1)^k$ with the symmetric function $s_\lambda[1+h_1+h_2+h_3+\cdots]$.
News flash! I said above that plethysm in in general intractable. Indeed, the Schur function expansion of $s_\lambda[1+h_1+h_2+\cdots]$ looks hopeless to me. However, taking the scalar product with $s_1^k$ results in a lot of simplification. I can show the following. The multiplicity of the representation of $S_n$ indexed by the partition $\lambda$ of $n$ in the $k$th tensor power of $V_n\oplus V_{n-1,1}$ equals the coefficient of $s_\lambda$ in the Schur function expansion of $(1+h_1+h_2+\cdots)\cdot \sum_{j=1}^k S(k,j)s_1^j$, where $S(k,j)$ is a Stirling number of the second kind. I wonder whether (After obtaining this is known result. , I noticed that it is essentially the same as Corollary 2 of the Goupil-Chauve paper mentioned in Vasu Vineet's comment.) Since for fixed $j$ we have $S(k,j)=\frac{1}{j!}\sum_{i=1}^j (-1)^{j-i}{j\choose i}i^k$, we can get explicit formulas for the multiplicities for fixed $\lambda$ that don't involve Stirling numbers. For instance, when $\lambda=(3)$ the multiplicity is $\frac{1}{6}(3^k+3)$, for $\lambda=(2,1)$ it is $3^{k-1}$, and for $\lambda=(1,1,1)$ it is $\frac{1}{6}(3^k-3)$. In particular, the multiplicity for $\lambda = (1^n)$ (i.e., $n$ parts equal to 1) is $S(k,n)+S(k,n-1)$.
