I have three questions about AES related to side channel attacks:
The values targeted by CPA are of the type $S(p\oplus k)$ where $p$ is a plaintext and $k$ a key byte, and $S$ maps bytes bijectively to bytes. One finds the correct key $k_0$ by correlating the Hamming weight of $S(p\oplus k)$ with the power consumption, as the absolute value of the correlation is expected to be the highest for the correct key $k_0$ at the time $t_0$ when the $S$-box output is processed in the CPU.
Now assume that for a second key $k_1\ne k_0$ the values of $S(p\oplus k_0)$ and $S(p\oplus k_1)$ differ only by a single bit for all plaintext bytes $p$. Then also their Hamming weights differ only by 1, and therefore the Hamming weights of $S(p\oplus k_0)$ and $S(p\oplus k_1)$ are strongly correlated. So whenever $k_0$ gives a high correlation between current consumption and predicted Hamming weight, so does $k_1$, which makes both keys difficult to distinguish, if one wants to know, which one is the correct one.
If $S$ happens to be linear, then $S(p\oplus k_0)\oplus S(p\oplus k_1) = S(k_0\oplus k_1)$ is independent of $p$. So if $S(k_0\oplus k_1)$ has Hamming weight 1, one is exactly in the bad situation (for the attacker) of the last paragraph. For $S$ bijective linear, this occurs for $8$ different key bytes $k_1$'s.
As the $S$-boxes have to protect the crypto-algorithm against linear and differential attacks, they are chosen such that $S(x)$ and $S(x\oplus\Delta)$ are "linearly as independent as possible". In particular, also their Hamming weights have as little correlation as possible. So if you have a high correlation with $S(x)$ (think $x=p\oplus k_0$), you will not have much correlation with $S(x\oplus\Delta)$ (think $\Delta=k_0\oplus k_1$), making different key bytes easily distinguishable.
Differently phrased, real $S$-boxes fulfill the basic assumption of DPA that wrong keys give random predictions for the current consumption, whereas linear $S$-boxes violate it.
In conclusion, any $S$-box good for "classical" cryptography is bad (=good target) for side-channel attacks like CPA, and vice versa. (There are some papers published about finding $S$-boxes good for both purposes, but to my knowledge none were found yet, and I'd be surprised if there will be.)
I do not know the article you ask about, but judging from the abstract the authors are only interested in an efficient (time+space) HW-implementation of the AES S-box, and not at all in security against side-channel attacks (they would mention it).
For the security against CPA it doesn't matter how an intermediate value you try to attack was created in the HW, only if it (or something else correlated to it) shows up leaking side-channel information (like power consumption).
Trying to fight side-channel attacks without using dynamic random (dynamic = freshly generated each time the algorithm is run) I wouldn't bet on. Just take a look at how easily all white-box implementations got broken using DPA-like techniques.
So the usual side channel attack associated with s-boxes is a cache based timing attack. This is something that is not really related to the non-linearity of the table itself; The table could just as easily be a memoized linear function, and it would still suffer from the same issue.
The issue is basically related to the layout of the table in the cache of the CPU that is processing the AES circuit. Different parts of the table reside in different parts of the cache, and which part of the cache is fetched is determined by the input to the s-box. This leaks a group of potential inputs to the s-box step.
So, the S-box is basically just a memoized function. This is done to speed up the processing time, as the non-linear function represented is relatively complicated/time consuming to implement. It is entirely possible to compute the S-box output discretely for every given input - However, this can result in a large performance penalty.
Some implementations choose compute the S-box discretely and to pay for this performance penalty, because the discretely computed version is not known to be vulnerable to cache based timing attacks.
Additionally, I believe that FPGA/ASIC implementations may be designed to use a table without suffering from cache based timing attacks (The cache in question is associated with a general purpose CPU and is hard for a programmer to explicitly control).
However, there are other side channel attacks such as Power Analysis. I think that linearity/non-linearity may play a greater part in SPA/DPA attacks because of the masking countermeasures involved and how those relate to non-linearity. I am not sure if these were the focus of your question, and if so, I will leave discussion of them to someone who is more knowledgeable.
So does computing the AES S-box discretely resist cache based timing attacks? It should. However, there may be other side channels that require other solutions in order to prevent leakage.
