Why isn't the Generalized Super Mario Bros. obviously in NP?
One reason why it is not obvious that reachability of SMB is NP is that we would need a complete formalization of SMB, which the paper does not provide. This makes sense, as the purpose of the paper is to showcase techniques for proving NP- and PSPACE-hardness of reachability problems in generalized video games, and to do that they only have to fully specify the portion of the video game that is nessecary for their reduction framework.

Another aspect is that a priori I would see no reason that e.g. Donkey Country would be PSPACE-hard (which the paper shows), but SMB not. Sure, likely the framework from the paper cannot be used directly to show SMB is PSPACE-hard, but that doesn't mean it isn't possible. So, it doesn't seem obvious to me why SMB is not PSPACE-hard, from which it follows that it isn't obvious that it lies in NP. (as long as you don't think it is obvious that PSPACE$\neq$NP, at least)



As for your specific reasons why SMB might not be in NP, the fact that other games are PSPACE-hard seems a good argument why a polynomial certificate may not exist. However, proving that there indeed cannot be a polynomial size certificate would be the same as proving PSPACE$\neq$NP, so there are no known techniques to do that. 

The second reason is related to the reason why the other games are PSPACE-hard. In general, solving two-player games can be done by reasoning "If P1 makes this move in turn 1, then for all moves P2 can do, pick a move for P2 s.t. $\ldots\ldots$ at the final move, P1 wins". This is the same as determining whether there is a satisfying assignment to a boolean formula with alternating universal and existential quantifiers: the true Quantified Boolean Formula problem (QBF). QBF is a PSPACE-complete problem.

This means that a 2-player game is PSPACE-hard if the above strategy of essentially going over all the moves is the only strategy to be guaranteed to win. The strategy of the 'computer' is of course limited in being only a simple function of the current state, but such a limited strategy can apparently be enough, as in the other games that are shown to be PSPACE-hard.



One question that may rise is why it is obvious that the problems lie in PSPACE. The authors cover this on page 2, but I will rephrase their argument here for the sake of completeness. Their main assumption is that the size required to describe the internal game state is polynomial in the input size. Their (somewhat informal) argument for this is that state changes of the game must controlled by a 'simple' and deterministic function of the player input. From the assumption it follows that we can solve a game reachability problem by making moves nondeterministically while maintaining the current game state. This means that the problem is in NPSPACE, and therefore in PSPACE as PSPACE=NPSPACE.