Higher Residuocity Problem w.r.t. a composite Modulus
Testing whether $q$ is a quadratic residue modulo $n$ is hard when $N$ is composite: it is as hard as factoring $N$, which is believed to be hard when $N$ is large.

The same is true for your problem.

If the factorization of $n$ is known and $k=2$, you can test whether $q$ is a quadratic residue; find all square roots, call it $y$, such that $y^2 \equiv q \pmod n$, then for each such square root $y$, test whether $y + c^2 \bmod n$ is a quadratic residue and find a square root of it, i.e., an $x$ such that $x^2 = y + c^2 \pmod n$, and then you will have a solution to your original problem.  This will be efficient if there aren't too many square roots, i.e., if $N$ doesn't have too many different prime factors.

Alternatively, assuming $n$ is squarefree and has known factorization $n=p_1 \cdots p_m$ and assuming $k$ is not too large, you can factor the polynomial $(x^2-c^2)^k-q$ over $\mathbb{Z}/p_i\mathbb{Z}$ (separately for each prime factor $p_i$ of $n$), then if this polynomial has a root modulo every $p_i$, combine solutions via the Chinese remainder theorem.