1. Super Mario Bros. is 40KB (PRG ROM is 32KB, and CHR ROM is 8KB). That said, I suppose if you were to compress the ROM, you probably would end up with value like 31KB.
2. Levels don't use RLE or LZ77, that would use too much space. Rather, the game uses commands like "from now on, use this ground fill pattern", "draw pipe here", "put a staircase", "put a goal". Super Mario Bros. uses two bytes per object, representing the following information: XXXXYYYY PSSSVVVV, where X is horizontal position within the page, Y is vertical position within the page, P moves to the next page, S is a command, and V is its parameter (length or number of an extended object). Y positions bigger than 0b1011 are used for special commands (as such parameters would be rendered out of bounds).
3. Graphics aren't compressed as they are stored in CHR ROM, and are directly accessed by the PPU (PPU cannot access RAM). However, as the graphics are 2bpp, they don't use as much space. Palettes are used to not restrict the entire game to 2bpp - note that 16x16 blocks have different color palettes. Some tricks are used to reduce the number of necessary tiles - for instance, clouds are the same thing as bushes, just with a different palette applied.
4. Demoscene is misleading. The way demoscene works is that most things are using procedural generation, meanwhile the levels in Super Mario Bros. are actually designed, and graphics were drawn by an artist, they aren't using some arbitrarily picked mathematical function chosen because it looked cool. The game has to be playable after all.