The NES in particular is probably not too difficult to upscale, because the graphics data is stored on its own ROM chip (sometimes RAM) in a well structured layout. SMB1 just uses a ROM chip containing many tile graphics which the CPU code addresses by tile index. It would be really easy for an emulator to use the same tile indices to address any arbitrary set of tiles loaded from a PNG. Some games use RAM, which makes it harder as you'd have to index the PNG by hash or something.

Compute motion vectors, faux depth, and add DLLS5 to it maybe? Could be pretty cool, or pretty horrific. Only one way to find out :)