The usual fast way is by modular arithmetic. For 10, the significant numbers are 2 and 5, which cube to give 8 and 125.
For $2$, all even numbers give a cube that is $0$ mod $8$. The odd numbers cube to themselves, modulo 8, so the valid answers modulo 8, are $0, 1, 3, 5, 7$, ie $5/8$ of the total.
For $5$, all multiples of $5$ cube to a multiple of $125$, but the remaining numbers are freely occurable. For example, there is a number whose cube is $3$, mod $125$. So for $5$, there are $100+1$ possible endings, or $101/125$.
Over $1000$, then there are $5/8 * 101/125$ = $505/1000$. For $100$, one reduces the case for 2 to modulo $4$, ie $0, 1, 3$, and for $5$, it's modulo $25$ (ie 21 solutions). There are thus $63=3*21$ possible endings for this.
When the fifth power is involved, a different thing happens. The powers of 5 must (in base 5), end in the digits $00,\; 01,\; 12,\; 33,\; 44$ only. The powers of $2$ are identical to above. So there are just $5$ possible endings for $25$ and $3$ possible endings for $4$, or just $15$ possible endings for $100$.
The ultimate form of this leads to the four cases where $10^a \mid x^n-x$, ie $-0001$, $-0000$, $-0625$ and $9376$, as the numbers $2$ and $5$ divide the value $x$.
When one handles a base with $3$ prime divisors, one does this for each of the three divisors.
Details
The process is weakly multiplicative. That means, if $x$ and $y$ are co-prime (ie $\operatorname{gcd}(x,y)=1$, then $f(xy)=f(x)\cdot f(y)$
Consider for example, the squares, modulo 20. This is weakly multiplicative, since we can write $f(20)=f(5) f(4)$, but not $f(20)=f(2) f(10)$. These are fairly easy to enumerate, since they all occur singly in the first six squares ($0$ to $5$).
0 1 4
0 1 2 3 4 5 0 0 16 4
0 1 4 9 16 5 = 6 1 5 1 9
Rows = mod 4, columns = mod 5
There are also 6 for modulo 15, which gives
0 1 4
0 1 2 3 4 5 6 0 0 6 9
0 1 4 9 1 10 6 1 10 1 4
Rows = mod 3, columns = mod 5
One sees that the modulo against $5$ does not depend on the other factors of the base. Moreover, there is a full column of the other primes for each case of 5. We can deal with the individual prime powers separately. So when we disect 10 or 14 below, instead of dealing with the full number, we can deal with the prime powers separately, and multiply the lot together.
One really has to worry if $\operatorname{gcd}(n, p^2-p) > 1$. In this case, there is a reduction of available choices.
For multiples of $p$, there is only one solution up to $p^n$ (ie -$0000000$ base $p$
When the gcd is $p$, then some $p^m$ divides $n$, and then there is only one string of $m+1$ digits, base $p$, for each primitive digit of $p$.
When the gcd ($x$) divides $p-1$, then there are just $(p-1)/x$ possible endings for non-multiples of $p$.
To give an example, suppose the power is $14$, and we're dealing with a base of 14. What is the count the available digits that $x^14$ might end in base $14$?
For prime $7$, the first rule tells us that all multiples of $7$ end in $00$ base $7$. This means that 1/7 of all numbers give rise to just 1 ending.
The second rule tells us that 7 divides $\operatorname{gcd}(14, 7^2-7)$. This means that there are just $7$ possible endings for 7th powers in base 7 (ie $00$, $01$, $24$, $25$, $42$, $43$ and $66$). We see that $6/7$ of the possible endings are removed, whether or not we count $00$: it's the same for each place.
The third rule tells us that 2 divides $\operatorname{gcd}(14, 7^2-7)$, so just half of the numbers (ie 3) are squares. These are $1$, $2$ and $4$.
All together, the modulo-7 restriction tells us that the only solutions for this problem, is that it is one of $1 + 42/7/2 = 4$ answers: here $00$, $01$, $24$ and $42$, base $7$
For $2$, the same rules tells us that there are just two answers over modulo $4$, that is, $00$ and $01$, base $2$
The chineses remainder solution can be used to find these $4*2=8$ solutions.
In response to your question: while there are many solutions where the squares have an odd number of digits, there are none for squares with an even number of digits such as 4.
Proof: Let $n \neq r$ be the number and its reverse, and let $10^{2k+1} < n^2 \neq r^2 < 10^{2k+2}$. Then $r^2$ ends with 1, 2, 5, 6 or 9 (not a 0, since then $n$ would start with 0). However, if $r^2$ ends with 1 then $n^2$ must start with 1, meaning $3.16 \times 10^{k} < n < 4.47 \times 10^{k}$; hence $n$ must start with either 3 or 4; but then $r^2$ ends with 9 or 6, a contradiction. By the same logic, if $r^2$ ends with 2 then $n$ starts with 4 or 5, meaning $r^2$ ends with 6 or 5. If $r^2$ ends with 5, $n$ starts with 7. If $r^2$ ends with 6, $n$ starts with 7 or 8. And if $r^2$ ends with 9, $n$ starts with 9. Since none of these are possible, no solution exists.
@tong_nor's answer demonstrates an infinite sequence of examples where the squares have an odd number of digits. In fact, there are many other such examples. A quick Python script suggests that all the the digits of the roots are always in the range 0 to 3. Proving this may be a good follow uo question.
Best Answer
The greatest possible sum of digits for a positive integer less than $313$ is $20$ (from $299$) so the minimum value you need to test is $293$. The sum of digits in this range is at least $3$ ($300$) and is at least $4$ for numbers other than $300$ so the greatest number you need to test is $309$
Either you are less than $300$ when, with units digit $a$ you have $290+2a+11=313$ and $a=6$, or greater than $300$ when $300+2a+3=313$, and $a=5$.