Not a complete answer, but here is a partial reduction of the problem, that yields a better complexity than your reference with respect to $d$.
First, you probably know about the related Discrete Logarithm Problem (DLP): given a cyclic group $G$ with generator $g$ and an element $x\in G$, find an integer $k$ such that $g^k=x$. There are algorithms to solve this problem in an arbitrary such group in time $|G|^{1/2}$. In $G=\mathbb{F}_p^\times$, there are heuristic algorithms to solve it in subexponential time, and in practice you might want to use one of these in some cases. The DLP in $G=\mathbb{Z}/N\mathbb{Z}$ is trivial.
Your problem is weaker: given an abelian group $G$, an integer $d$ and an element $x\in G$, determine whether $x$ is a $d$-th power in $G$ and find a $d$-th root. Clearly if you can solve the DLP, then you can solve the power problem.
Note that if you have an exact sequence
$$
1 \to H \to G \to Q \to 1
$$
where you can compute images and preimages in polynomial time, then you can reduce the power problem in polynomial time to the same problem in $H$ and $Q$.
If you can compute images by both morphisms, and preimages of the injective morphism in polynomial time, then you can reduce the DLP in $G$ to the same problem in $H$ and $Q$.
Now I will start the reduction.
Your general problem is the $d$-th power problem in $G = (\mathbb{Z}/n\mathbb{Z})^\times$ ($n$ given in factored form). By CRT and the remark above, the problem is reduced in polynomial time to the case where $n$ is a prime power.
Now if $G = (\mathbb{Z}/p^e\mathbb{Z})^\times$, let $G_0=G$ and for $i\ge 1$, $G_i = 1+p^i\mathbb{Z}/p^e\mathbb{Z}\subset G$. Then we have $G_0/G_1\cong (\mathbb{Z}/p\mathbb{Z})^\times$, for $i\ge 1$ we have $G_i/G_{i+1}\cong \mathbb{Z}/p\mathbb{Z}$, and $G_e=1$. Since all these isomorphisms are computable and the DLP is trivial in $\mathbb{Z}/p\mathbb{Z}$, we are reduced to the case where $e=1$.
If $G = (\mathbb{Z}/p\mathbb{Z})^\times$, let $d = \prod_i q_i^{a_i}$ and $p-1 = \prod_i q_i^{b_i}$ be the factorisation into coprimes of $d$ and $p-1$. This means factorisations as displayed, where the $q_i$ are pairwise coprime but not necessarily prime. Such a factorisation is computable in polynomial time. (Depending on whether you are willing to use probabilistic / heuristic algorithms, you may even want to use a complete factorisation into primes here). Clearly the $d$-th power problem reduces to the $q_i^{a_i}$ power problem for each $i$, i.e. we can assume that $d=q^a$ and $q^b$ divides $p-1$ exactly (i.e. divides it and is coprime to the quotient).
There are some nice cases:
- First case: $b=0$, i.e. $d$ is coprime to $p-1$. In this case, every element of $G$ is a $d$-th power, and you can obtain them in polynomial time by writing $ud+v(p-1)=1$, so that $x = (x^u)^d$ for all $x\in G$.
- Second case: $a=b$, i.e. $d$ divides $p-1$ and is coprime to $n=(p-1)/d$. Write $ud+vn = 1$, and let $x\in G$. If $x=y^d$ for some $y\in G$, then $(x^u)^d = x$. So $x$ is a $d$-th power if and only if $x^u$ is a $d$-th root of $x$, and we can solve the problem in polynomial time.
In general, you can repeatedly use the second case to reduce to $a<b$. If $a$ was a multiple of $b$, you are done.
Otherwise, I do not have anything clever to propose. Here is a possibility, which recovers classical algorithms for square roots and other fixed powers. Assume that you are given a generator of the $q^b$-subgroup $H$ of $G$ (this is possible in polynomial time if you are willing to accept a probabilistic algorithm or assume GRH). Now simply solve DLP in $H$ by repeatedly using the exact sequence $1\to H[q] \to H \to H^q\to 1$. The running time is $q^{1/2}(\log (pq))^{O(1)}$ using generic algorithms.
