One can't have $k \ge 2n$ (proof in a moment). An integer solution at the end.

If $k \le n$ then one can choose $y_1,y_2,\cdots,y_n$ and $x_{n+1},x_{n+2},\cdots,x_{2n}$ and solve for $x_1,x_2,\cdots,x_n$. I arbitrarily decided to try this with $x_3=3,x_4=4$ Varying $y_1,y_2$ I find

$y_1,y_2;x_1,x_2,x_3,x_4=8,20;\frac{21-\sqrt{437}}{2},\frac{21+\sqrt{437}}{2},3,4$ Many other choices work as well (for example $11 \le x_1 \le x_2$).

**later** It should be easy to find solutions with $k=n$ although I have no idea about the integer case: Pick $y_1,\cdots,y_n$ not too small and no two too close together (say $y_i=i$) Then the values $y^j_1 + y^j_2 + \cdots + y^j_n$ determine the coefficients of the monic polynomial $f(t)=\prod_1^n(t-y_i)$ and vice versa. The $y_i$ are the $n$ roots of $f$. Now pick $x_{n+1},\cdots,x_{2n}$ positive but "small enough".Then the desired equations $x^j_1 + x^j_2 + \cdots + x^j_n=y^j_1 + y^j_2 + \cdots + y^j_n-\sum_1^nx_{n+k}^j$ determine the coefficents of some monic polynomial $g(t)$ whose roots are $x_1,\cdots,x_n$. If the prechosen values are small enough (maybe $x_{n+k}=\frac{k}{100^n}$) then the coeffcients of $g$ should be only slightly preturbed from those of $f$ so the roots $x_1,\cdots,x_n$ should be only slightly preturbed from $y_1,\cdots,y_n$

Here is my argument for why we can't expect $k=2n$: In this case the equations and values for $y_1,...,y_n$ will determine $x_1,x_2,\cdots ,x_{2n}$ up to order. But we know a solution with $n$ zeros so the other solutions must be the same rearranged.

The (multi)sets $A=[0,4,5]$ and $B=[1,2,6]$ have equal sums of $j$th powers $j=0,1,2$. Thus the same is true for $A\cup 4A \cup 5A \cup 6A$ and $B\cup 4B \cup 5B \cup 6B$. This remains true for $j=1,2$ if we drop the common terms and the 4 $0$s leaving $$[16,20,20,25] \text{ and }[1, 2, 6, 6, 8, 10, 12, 36]$$

I haven't managed a similar trick for $[0,2,9,11]$ and $[1,4,7,10]$ (equal sum of powers for $j=0,1,2,3$) or other similar examples.

A potentially useful technique for the integer case: One way to verify the claim about $[6,2,1]$ and $[5,4,0]$ is to observe that the polynomial $p(t)=t^6-t^5-t^4+t^2+t-1=(t-1)(t^2-1)(t^3-1)$ has a triple root at $t=1$. In our case, consider the polynomial $\sum_1^{2n}t^{x_i}-\sum_1^n t^{y_i}-n$. It has a $k+1$-fold root at $t=1$ precisely if the desired equations hold. Hence $f(t)=t^{36}-t^{25}-2t^{20}-t^{16}+t^{12}+t^{10}+t^8+2t^6+t^2+t-4$ has a triple root at $t=1$. In fact $f=(t-1)(t^2-1)(t^3-1)(t^2-t-1)g(t)$ where $g(t)=t^{28}+2t^{27}+\cdots+13t^4+11t^3+9t^2+7t+4$ has (weakly) unimodal non-negative coefficients and the triple root at $t=1$ comes from the same $(t-1)(t^2-1)(t^3-1)=p(t)$.

nofor $n=1$ by Fermat's Last Theorem. – Tony Huynh Feb 1 '11 at 1:13