Um, wrong, even assuming H40, the bandwidth is only somewhat larger (around 7KB vs around 6KB, if memory serves well), and in H32 they're practically identical. If the Mega Drive had been equipped with 128KB of VRAM you'd be right since in that mode it does indeed double bandwidth :P Alas…
But yeah, even that considered, PAL is a completely different beast than NTSC, it has over twice as much vblank time and transfer bandwidth during vblank is proportionately larger (at the expense of lower framerate).
Nah, the original demo already changed all 16 colors at a whim (and a lot of the glitchy polygons came from there too, though the format containing non-convex polygons didn't help matters).
That said, there are pre-built solid tiles for all 16 colors (rather than just background color), which is indeed what's being used to fill in the large solid areas.