PART 1. I consider the generic case. The problem is as follows We randomly choose $B\in M_2(\mathbb{Z})$ and let $A=B^k$. $k,A$ are known and $B$ is unknown; find the $X$'s such that $X^k=A$.
i) Calculate $p(x)$, the characteristic polynomial of $A$, and let $q(y)=p(y^k)$.
ii) Factorise in irreducibles over $\mathbb{Z}$: $q(y)=q_1(y)\cdots q_l(y)$.
Generically, when $k$ is odd, there is exactly one factor $q_i$ of degree $2$ and, when $n$ is even, there are exactly two factors $q_i,q_j$ of degree $2$ corresponding to $2$ opposite values of $X$.
For example, let $q_1(y)$ be one factor of degree $2$ and let $Q$ be its companion matrix. Then, there is an unknown matrix $R\in M_2(\mathbb{Q})$ s.t. $A=RQ^kR^{-1}$.
iii) Solve the equation $RQ^k-AR=0$ ($4$ linear equations in the $4$ unknowns $(r_{i,j})$'s). Generically, we obtain a vector space solution of dimension $2$, that is, a set of solutions that depends on $2$ parameters $u,v$.
iv) Randomly choose $u,v$; we obtain (except if we are very unlucky; in this case, make another choice) a particular matrix $R$ and we deduce the essential solution $X=RQR^{-1}$.
PART 2. If $k$ is not given,we calculate $\delta=\det(A)$; we are looking for the $k$ such that $\delta$ is a power $k^{th}$. There is only a finite number of possible values of $k$, except when $\delta=\pm 1$.
For $\delta=1$, every value of $k$ gives an essential solution. For $\delta=-1$, each odd value of $k$ gives an essential solution.
PART 3. If we randomly choose $A$, then, generically, $q$ has no factors of degree $2$.