What are the $393$ trillion possible answers when computing $13^{th}$ root of a number?

We have to compute the $13$-th root of an unknown number $N$ such that $10^{199}\le N<10^{200}$ so that $\;10^{199/13}\le N^{1/13}<10^{200/13}$ : all the choices are not possible but only the values from $ 2,030,917,620,904,736\;$ to $\;2,424,462,017,082,328$. This gives at most : $$10^{200/13}-10^{199/13}\approx 393,544,396,177,593\quad\text{possibilities}$$ $$-$$ For something 'simpler' suppose known the $60000$ digits of the perfect power $\;N=k^{11001}\;$ and try to find the positive integer $k$. You'll notice that $k$ can only take the values from $284420$ to $284478$.

Remembering the two last digits of the $11001$-th powers of $\;(284420+i)\;$ for $i$ from $0$ to $58$ : $$0, 21, 72, 23, 24, 25, 76, 27, 28, 29, 0, 31, 32, 33, 84, 75, 36, 37, 88, 39, 0, 41, 92, 43, 44, 25, 96, 47, 48, 49, 0, 51, 52, 53, 4, 75, 56, 57, 8, 59, 0, 61, 12, 63, 64, 25, 16, 67, 68, 69, 0, 71, 72, 73, 24, 75, 76, 77\quad\text{(and some tricks to distinguish the degenerate cases like $0$) }$$ should help you, after just a smart glance at the $60000$ digits of the $11001$-th power, to provide instantly the wished $11001$-th root !

But to choose between $59$ values we don't really need to memorize all these values (nor even require $N$ to be a perfect power). Mental calculators usually know their common logarithms and may use : $$N^{1/11001}\approx 284419+59.53\;\log_{10}N_2,\\\quad\text{with $N_2$ defined by $\,N=N_2\;10^{60000-1}\;$ and}\;\,1\le N_2<10$$ this is easily obtained from $\;N^{1/11001}\approx 10^{\large{\frac{60000-1}{11001}+\frac{\log_{10}(N_2)}{11001}}}\approx 10^{\large{\frac{60000-1}{11001}}}\left(1+\frac{\ln(10)}{11001}\log_{10}(N_2)\right)$.
A working precision of $2$ digits for $N_2$ should be enough while replacing $59.53$ by $60$ gives an error bounded by $\,0.48$.

We may thus "reduce the possibilities" by using the most significant digits and, for a perfect power only, by exploiting the less significant ones (as explained by Barry Cipra).
It should be clear that all this doesn't explain the speed of A. Lemaire and others who used specific techniques like memorizing the different $13$-th roots possible for the first digits (specifically for $200$ digits numbers) as well as for the last digits.

Many of the methods used are neatly exposed in Ron Doerfler and Miles Forster article :
"The $13$-th Root of a $100$-Digit Number" starting with the methods used by Wim Klein (from Ron Doerfler's blog). Let's conclude with some of his wise words :

“What is the use of extracting the $13$-th root of $100$ digits? ’Must be a bloody idiot,’ you say.
No. It puts you in the Guinness Book, of course”

This is just an elaboration on Raymond Manzoni's answer, addressing the OP's question whether the journalist misunderstood something.

Here are the lede paragraphs from the news story (which features a photo illustration of Lemaire pondering the 200-digit number):

When the answer is 2,407,899,893,032,210 you know the question is tough.

Not so tough, however, that Alexis Lemaire could not work it out in his head. His challenge yesterday was to come up with the 13th root of a computer-generated 200-digit number.

And, with 393 trillion possible answers to choose from, the PhD student made it almost look easy.

The "393 trillion" almost certainly came from a press release prepared by the sponsor of the challenge; no reporter (except maybe me) has the time or the expertise to make such a calculation (and I would probably get it wrong). Given that the 13th root of the 200-digit number was an integer, it seems fairly clear that what the computer did was pick a (random?) number $n$ such that $10^{199}\le n^3\lt10^{200}$, so that there are $\lfloor10^{200/13}\rfloor-\lfloor10^{199/13}\rfloor\approx393$ trillion choices for $n$.

It's perhaps worth noting, though, that $a^{13}\equiv a$ mod $10$ for all $a$, which means that that a quick look at the final digit of the 200-digit number tells you the final digit of the answer. So in a sense this quickly cuts the number of possible answers down to around $39.3$ trillion. And in this case, in fact, the 200-digit number ends in a string of thirteen $0$'s preceded by a $1$, which means the answer necesarrily ends in $10$, thus cutting the number of possibilities to a "manageable" $3.9$ trillion....