I was wondering about whether the usage of a precomputed sbox (kind of a lookup table) could be a serious security issue when using AES.
Well, that rather depends on the type of side channel attacks you are interested in protected against.
You specifically mention Power Analysis (SPA and DPA) type attacks; the first obvious question would be: could those attacks actually be performed by the type of adversary you are trying to protect? After all, to perform those attacks, the attacker needs to make extremely precise (and extremely high resolution) measurements of the current drawn by the circuit; is this a realistic scenario?
Sometimes it isn't. If we're talking about crypto that'll be used in a Web server in a physically secure location, there's no way an attacker could get physical access (and if he could, there are far more damaging attacks an attacker could do). On the other hand, if we're talking about crypto on a Smart Card (where the power is externally supplied, potentially by the attacker), then power analysis attacks are quite realistic.
And, if we really do need to protect against such invasive attacks, we need to worry about a lot more than just how the sbox is computed. If you're running on a general CPU, then what an attacker with that level of access might be able to do is directly monitor the memory bus (and just read the keys are they are being read from memory); to prevent that level of attack, we generally need the entire crypto circuit be in a special enclave that the attacker can't break in (for example, epoxy-encapsulated).
And, power analysis attacks can allow the attacker to deduce the settings of various gates; in the standard AES implementation, the first thing you do is xor the plaintext with 128 bits of the key; if the attacker can read those first 128 bits, he gets 128 bits of the key (and with AES-128, that's all of it). Because of this, when we do a DPA-resistant implementation, we implement a blinded or threshold implementation (where we stir in some randomness at the start of the operation; this randomness doesn't affect the final result, however it does affect how the intermediate values are represented, where each logical bit is spread over several physical bits (so that the setting of any internal bit, or any set of k bits, are uncorrelated to the logical operation being performed). Now, this doesn't actually stop all DPA attacks; we hope it makes it sufficiently difficult that the attacker won't be able to collect enough data samples (e.g. encryptions based on the same key) to actually deduce anything.
Now, table lookups don't work well in this blinded/threshold scenario, and so (to answer the question you originally asked) we tend to compute things on the fly.