It is at least true for $k = 2\ell$ and $p \in (1,2]$. The restriction on $k$ is just to make the computation simpler, and shouldn't be too hard to extend to $k$ being odd. The restriction to $p\in (1,2]$ is essential in the method of proof below.
By triangle inequality it suffices to prove that for every $0 < j < \ell$ you can interpolate
$$ \| \triangle^ju \|_p \leq \epsilon \|\triangle^\ell u\|_p + C(\epsilon,j) \|u\|_p $$
Let $P_n$ denote the standard Littlewood Paley projectors with $n \in \mathbb{N}$, then we have (the constant $C$ differs from line to line, but are "universal")
$$ \begin{align}
\| \triangle^j u\|_p &= \| \sum_n P_n \triangle^j u\|_p \\
& \leq C \sum_{n} 2^{2nj} \| P_n u\|_p \\
& \leq 2^{2n^*j}C \sum_{n = 0}^{n^*} \|P_n u\|_p + C \sum_{n = n^* + 1}^\infty 2^{2nj} \|P_n u\|_p \end{align} $$
where $n^*$ is to be determined. The first term can be bounded (very roughly) by
$$ (n^* + 1) 2^{n^* j} C \|u\|_p; $$
the second term we control with (throughout $C$ is independent of $n^*$)
$$
C\sum_{n = n^* + 1}^{\infty} 2^{2n(j-\ell)} 2^{2n\ell} \|P_n u\|_p \leq
C\left( \sum_{n > n^*} 2^{4n(j-\ell)} \right)^\frac12 \left( \sum_{n > n^*} \|P_n \triangle^\ell u\|_p^2\right)^\frac12 $$
by Cauchy-Schwarz. Using that $j-\ell < 0$ the first factor converges and can be bounded by $2^{2n^*(j-\ell)}C $ for some $C$ independent of $n^*$. For the second factor we can use the fact that $p \leq 2$, which implies via Minkowski's inequality that
$$ \left( \sum_{n > n^*} \|P_n \triangle^\ell u\|_p^2\right)^\frac12 \leq \| \left( \sum_{n > n^*} |P_n \triangle^\ell u|\right)^\frac12 \|_p $$
the right hand side now is dominated by the square function and for $p > 1$ we can use the square function estimate to conclude that it is bounded by $C \|\triangle^\ell u\|_p$. Putting everything together we have that for some universal constant $C$, independent of $n^*$, we have
$$ \|\triangle^j u\|_p \leq (n^* + 1) 2^{2n^*j} C \|u\|_p + 2^{2n^*(j-\ell)} C \|\triangle^\ell u \|_p $$
Now it suffices to take $n^*$ sufficiently large so that the coefficient in front of $\|\triangle^\ell u\|_p$ is less than $\epsilon$.