Complexity of a variant of the Mandelbrot set decision problem?
Let's look at $M$ for fixed $k$ first.

Given a fixed $k$ in unary, the problem essentially reduces to figuring out the algebraic set $|P_c^{(k)}(0)| = 2$.  Since the level sets 'at infinity' are properly nested, the question becomes a membership test in an algebraic set.  The issue is that the minimal polynomial is of degree $2^k$.  However, one can represent it as a straight-line problem of size $k$.

So then the question becomes: what is your arithmetic model?  You'll need arbitrary precision arithmetic to do this 'right', and then counting bit operations or counting "real number" operations will give radically different answers [NP-hardness is rather fragile that way, unlike 'computability'].

For arbitrary $k$, things get messier still.  It really depends on whether one would have a uniform modulus of continuity; if that were the case, then the Mandelbrot set would be locally connected, which would indeed be a breakthrough.  So I rather think that that problem is open.

Looking up the Yampolsky and Braverman book is a good idea in any case.