https://en.wikipedia.org/wiki/Paillier_cryptosystem

Paillier cryptosystem exploits the fact that certain discrete logarithms can be computed easily.

If I were to select $$g \in \mathbb{Z}_{n^2}^*$$ where $$n$$ divides the order of $$g$$, then the discrete log is easy (w.r.t base $$g$$) if I understand correctly.

But if I were to select any random value $$r \in \mathbb{Z}_{n^2}^*$$ where $$n$$ does not divide the order of $$r$$, are we then able to say anything about the difficulty of the discrete log?

I'll assume the typical Paillier set up that $$n=pq$$ with $$p$$ and $$q$$ prime numbers $$(p-1)\not\!| q$$ and vice-versa.

The recovery of a discrete logarithm $$x$$ of a general element $$a$$ with respect to a generator is equivalent to the recovery of three values: $$x\equiv\cases{x_\lambda\pmod{\lambda(n)}\\ x_p\pmod p\\ x_q\pmod q}.$$

If one knows the values of $$p$$ and $$q$$ then $$x_p$$ and $$x_q$$ are easy to recover using Fermat quotients or $$p$$-adic version of the logarithmic Taylor series. The best known methods to recover $$x_\lambda$$ rely on the number field sieve and for cryptographically sized* $$p$$ and $$q$$, this should be infeasible. If one picks a generator such that the order of the generator divides $$n$$, this means that $$x_\lambda$$ can be ignored and discrete logarithms with respect to this generator can easily be computed by anyone who knows $$p$$ and $$q$$.

In your first case where $$n$$ divides the order of $$g$$, this only tells us that $$x_p$$ and $$x_q$$ cannot be ignored. It does not ensure that $$x_\lambda$$ can be ignored and hence our problem could still be intractable.

In your second case where $$n$$ does not divide the order of $$r$$ this tells us that either $$x_p$$ can be ignored or $$x_q$$ can be ignored (possibly both can be ignored). It does not ensure that $$x_\lambda$$ can be ignored and our problem could still be intractable.

In general:

• if $$p$$ does not divide the order of the generator, then $$x_p$$ can be ignored,
• if $$q$$ does not divide the order of the generator, then $$x_q$$ can be ignored,
• if $$\lambda(n)$$ does not divide the order of the generator, then $$x_\lambda$$ can be taken ignored.

Also note that if we happen to know a bound on the size of $$x$$, then it may not be necessary to recover all three components. e.g. if we know that $$x then recovery of $$x_p$$ and $$x_q$$ allows us to uniquely recover $$x$$ from the Chinese remainder theorem.

*- Note that $$p$$ and $$q$$ have to be larger moduli than can be attacked with the number field sieve rather than simply $$n$$ being a larger modulus than can be attacked with the number field sieve.