How to find the smallest $r$ such that $o_r(n) > \log^2(n)$ in polynomial time?
It appears you are asking because you are interested in understanding the famous "PRIMES is in P" paper and why its algorithm runs in polynomial time.  Finding such an $r$ is exactly step 2 of their algorithm.

As was explained to you previously on Math.SE, the paper explains why its algorithm runs in polynomial time.  The explanation is terse and assumes the reader will be able to make the missing connections, but the key ideas are there.  If you keep reading in the paper it presents the crucial fact: the smallest such $r$ has size at most $r \le \max\{3, \lceil \log^5 n \rceil\}$ (see Lemma 4.3, which is just a few paragraphs after the statement of the algorithm).  Consequently, there is a very simple algorithm to find such an $r$: try each $r$ in turn, i.e., try $r=1$, then $r=2$, then $r=3$, checking each candidate value of $r$ to see if it satisfies the condition.  Output the first one you find that satisfies the condition.  Thanks to the fact in the paper, you'll only need to try $O(\log^5 n)$ many such $r$, which is polynomially many.  Moreover, you can check the condition for a given $r$ in polynomial time.  Thus, the total running time is polynomial in $\log n$.

In the future, if you have a question about some aspect of the paper, please tell us in the question what paper you are reading.  More generally, tell us about the context around your question and the motivation. Also, when asking about some aspect of a paper, I encourage you to read the entire paper before asking -- sometimes the answer to your question might be found later in the paper.