I've been trying to prove the above by induction on $k$. I think I've proved it for $k=1$ (I put the proof below for completeness), but I don't see to go from assuming that $f(x)=x^{p^n}-a$ is irreducible to showing that $f(x)=x^{p^{n+1}}-a$ is also irreducible. I'd appreciate any hint towards this. Thanks in advance.
Let $\alpha \in \bar{K}$(the algebraic closure of $K$) be a root of $f(x)=x^p-a$. Then $\alpha$ is the unique $p^{th}$ root of $a$ in $\bar{K}$. Assuming $f$ reducible, we can express $f$ as a product of irreducible polynomials. The element $\alpha$ is a root of each factor. As these irreducible factors are also monic, they must be the minimum polynomial of $\alpha$ over $K$, namely, $f(x)=(f^{\alpha}_K)^n$ in $K[x]$ for some $n \leq p$.
Let $f^{\alpha}_K(x)=x^d+k_{d-1}x^{d-1}+...+k_0$ where $d \leq p$ and $k_{d-1},...,k_0 \in K$. Then $x^p-\alpha = (f^{\alpha}_K)^n = (x^d+k_{d-1}x^{d-1}+...+k_0)^n = x^{dn} +$ other terms in lower powers of $x$. Hence $nd=p$, so either $n=1$ and $d=p$ or $n=p$ and $d=1$.
If $n=p$, by the corresponding condition on $d$, $f^{\alpha}_K(x)=x+k$ for some $k \in K$. Thus \begin{align*} (f^{\alpha}_K(x))^n &= (f^{\alpha}_K(x))^p \\ &=(x+k_0)^p \\ &=x^p+(k_0)^p \end{align*} where we used that the Frobenius map is a field homomorphism in fields of characteristic $p$. The equality $f^{\alpha}_K(\alpha)=0$ implies $\alpha^p=-(k_0)^p$, but this contradicts that $a$ isn't a $p^{th}$ power in $K$. If $n=1$, $f$ is equal to an irreducible polynomial and so must be irreducible itself.
Over some larger field, $X^{p^k}-a=(X-b)^{p^k}$. So if $X^{p^k}-a$ factors over $K$ it has a factor of the form $(X-b)^r$ in $K$ for some $r$ with $1\le r\le p^k-1$. That entails $b^r\in K$. But as $b^{p^k}\in K$ we get $b^g\in K$ for $g=\gcd(r,p^k)$. Then $g=p^l$ where $0\le l\le k-1$, and from $b^{p^l}\in K$ we deduce $b^{p^{k-1}}\in K$. That's a $p$-th root of $a$.