Why is computing pure Nash equilibria NP-complete?
These are my two comments as an answer:

Of course you are right that if the strategic form (also called the normal form) is given explicitly then one can just check all pure strategy profiles. In that case, the problem of deciding if there is a pure equilibrium is clearly not likely to be NP-hard. 

However, the paper shows in Theorem 3.1 hardness for graphical games (called in the paper, games in graphical normal form (GNF)), which are succinctly represented games. (It might not be the best phrasing in the statement of Theorem 3.1 to say "even for", which is fine as regards constant values of parameters, but not for the representation type itself).

In general, if each of $n$ players has $m$ actions then the the strategic form has $nm^n$ entries, but a graphical game has $O(nm^{d+1})$, where $d$ is the maximum degree in the graph. So for constant $d$, the graphical game representation is exponentially smaller than the strategic form. In their reduction $d$ can be 3 (and $m$ can also be 3, so only $n$ needs to vary).

For the strategic form (standard normal form, SNF, as they call it in the paper) they show that the problem is easy (Theorem 5.1), which is straightforward as you noted.

SNF and GNF are compared on page 6 of the paper.