Nice problem. Below I present my solution—I didn't optimize the writing. I first prove a lemma which will be used repeatedly. Note that for $k=1$, we simply take $x_1=n$, so assume $n\ge 2$ in the sequel. Lemma. Given any positive integers $n,k$, let $r=\lfloor \sqrt[k]{n}\rfloor$. Then, $n-r^k\le kn^{\frac{k-1}{k}}$. Proof. It is evident that $r^k\le n<(r+1)^k$. Consider now the function $\varphi(z) = z^k$. Then using Mean Value Theorem, \[ n-r^k = \varphi(\sqrt[k]{n}) - \varphi(r) = \left(\sqrt[k]{n}-r\right)\sup_{r\le z\le \sqrt[k]{n}} \varphi'(z)\le kn^{\frac{k-1}{k}}. \]Equipped with lemma, we now greedily construct the desired $k$-tuple $(x_1,\dots,x_k)$. Let $M\triangleq 2^{k-1}\sqrt[k]{n}$, the global upper bound on $x_i$. At first step, take $r=\lfloor \sqrt[k]{n}\rfloor$ and apply the lemma to reduce the problem to finding a $(k-1)$-tuple $(x_1,\dots,x_{k-1})$ for which \[ x_1 + x_2^2 + \cdots + x_{k-1}^{k-1} = n-x_k^k = \Delta_k\le kn^{\frac{k-1}{k}}, \]where we applied the lemma in the last step. Note that $x_k = \lfloor \sqrt[k]{n}\rfloor \le M$. At each step $t$, we will verify that $x_t\le M$, the global upper bound. Note that if $\Delta_t$ reaches zero, then we simply stop and set the rest of the variables to zero. Next, we set $x_{k-1} = \lfloor \sqrt[k-1]{\Delta_k}\rfloor$ and denote the resulting term by $\Delta_{k-1}$. We now apply Lemma with $k-1$ in place of $k$, and $\Delta_k$ in place of $n$ to find that \[ \Delta_{k-1} = \Delta_k - x_{k-1}^r \le (k-1)k^{\frac{k-2}{k-1}}n^{\frac{k-2}{k}}. \]We now assign $x_{k-2} = \lfloor \sqrt[k-2]{\Delta_{k-1}}\rfloor$. What we need to check is that $x_{k-2}\le M$. It suffices to prove \[ (k-1)^{\frac{1}{k-2}}k^{\frac{1}{k-1}}\sqrt[n]{k}\le M. \]To that end, we prove a stronger claim: \[ \prod_{2\le i\le k} i^{\frac{1}{i-1}}\le 2^{k-1} \Leftrightarrow k-1 \ge \sum_{2\le i\le k}\frac{\log_2 i}{i-1}. \]Note that $2^{i-1}\ge i$ for all $i\ge 1$. So, $i-1\ge \log_2 i $. This establishes the inequality above. Hence, at each step $x_j$'s that are assigned greedily remain below the upper bound $M$, so this construction indeed works.