If $p$ is prime, then $x^k\equiv c \pmod p$ has a solution if and only if $c^{(p-1)/g} \equiv 1$ where $g=\gcd(k,p-1)$. The solution is given by $x \equiv \sqrt[g]{c^h} \pmod p$ where $h^{-1} \equiv k/g \pmod{p-1}$. You can take $g$th roots in polynomial time using an extension of the Tonelli-Shanks algorithm; see On taking roots in Finite Fields by Adleman, Manders, and Miller. (Strictly speaking, this algorithm requires either reasonable number theoretic assumptions or randomization.) Given one solution $x$, the other solutions will have the form $x \beta^i$ where $\beta$ is an element of order $g$ modulo $p$.
If $p^m$ is a prime power and $\gcd(p,k)=1$, then you can use Hensel lifting to test whether $x^k \equiv c \pmod{p^m}$ has a solution. In particular, let $x_i=x \bmod p^i$ and $c_i=c \bmod p^i$ and $y_i = (x_{i+1} - x_i)/p$ and $d_i = (c_{i+1} - c_i)/p$. Now find $x_1$ such that $x_1^k \equiv c_1 \pmod p$. If this has no solution, then neither does $x^k \equiv c \pmod{p^m}$, so we can terminate immediately. Otherwise, we're next going to try to find $x_2$ such that $x_2^k \equiv c_2 \pmod{p^2}$. Writing $x_2 = x_1 + p y_1$ and $c_2 = c_1 + p d_1$, we obtain the equation
$$(x_1 + y_1 p)^k \equiv (c_1 + d_1 p) \pmod{p^2},$$
or equivalently,
$$k x_1 y_1 \equiv (c_1 - x_1^k)/p + d_1 \pmod p.$$
If $k x_1 \not\equiv 0 \pmod p$, then we can let $y_1 = ((c_1 - x_1^k)/p + d_1) \cdot (k x_1)^{-1} \bmod p$ and we have a solution for $x_2$. Otherwise, test whether $x_1^k \equiv c_2 \pmod{p^2}$; if it is, then setting $x_2=x_1$ gives a solution, otherwise there is no solution and we can terminate. Repeat the same process to find $x_3$, then $x_4$, etc., until you have found $x_m$. While there may be multiple possible solutions for $x_1$, there is no need to branch and try all of them, because either all will be extendable to $x_m$ or none will.
I am not sure what to do if $\gcd(p,k)=1$. Perhaps someone else can fill in this gap.
If $N$ is a product of prime powers $p_1^{m_1} \cdots p_n^{m_n}$, then you can use the Chinese remainder theorem to check for a root modulo each of the $p_j^{m_j}$. A root exists modulo $N$ if and only if it exists modulo each prime power; and once you've found a solution for each prime power, you can combine them with the CRT to obtain a solution modulo $N$.
Proof for first paragraph: If $p$ is prime, then there exists an element $\alpha$ of order $p-1$; assuming $x \equiv \alpha^X \pmod p$ and $c \equiv \alpha^C \pmod p$, we find that the equation has a solution if and only if $Xk \equiv C \pmod{p-1}$ has a solution, which is equivalent to the stated condition in the first paragraph.
