AlexHW: I think you may be missing the aspect of this exercise that is about the design/typographical concept of "Color"* and feature distribution : that's the effect of Helm's proposed restrictions. It's true that this is an aspect that -should- be naturally pulled in, but looking at all sorts of art, it is not; and especially for upsizing pixel art, a naive attempt at upscaling (such as the one Mr.Beast posts) produces poor "color" and feature distribution that has poor rhythm.
* the overall impression of an area's "general value" when you squint at something.
I also agree with Erekt's point, which is similar to mine but with a different slant.
Anyway, I thought I'd see how dither goes with this exercise. It turned out to take 30min. Could definitely spend more time on it but don't have more time right now.
Side-by-side, upsized on left:

Original:

Upsized:

Comments:
Initial upscale done via scale2x. Previously I would have felt unduly constrained by this, but the cleanup process felt pretty natural this time. Focusing on working with blobs probably prevented a bunch of trivial fiddling.
Using blobs of dithering rather than thinking of it in more realist terms forced me to .. hmm. 'meta-dither' (a technique that should be familiar to people who like stylized / 'custom / layered ' dither shapes. Result: painting-like vagueness that is mostly pleasing
I fixed some of the flaws of the original in the process, flipping the lighting on the left around since that works decently at double res.
The blockiness underneath the platform was intentionally preserved.
The 2,1,2,1.. rhythm on the archway probably could stand a little tuning.
I felt there should be a few more thin elements, but can't really see any opportunity for them. Similarly, the black along left edge of right side of arch feels a bit too heavy, but couldn't find a satisfactory solution.
Angularity aided rhythm but I didn't really find a algorithm that could be applied consistently to produce consistently good results. It fights some of the planes I'd prefer.
Overall, seems somewhat Yoshi's Island -ish