In general, if you have to ask how hard something is going to be, the answer is "very hard". The only hacking jobs that are easy are the ones where you already have an idea of how to do it.
For SMB2 NES.... adding a menu option means changing drawing routines, input routines, and actually adding the save.
For All-Stars, isolating a single game would be mostly just finding the SMB2 entry point and jumping to it earlier. The change would be incredibly easy, but finding where to make that change would be very rough. Best approach I know of is to dump a tracelog and pour over it.... and... well.... looking at pages of undocumented asm code is hard enough, but when you're a noob you don't even really know what you're looking for.... so you'll just be staring into space.
Modifying All-Stars would definitely be easier, but that's only relative to the NES hack. I'm not sure I'd recommend either of these as a beginner project.