Similar to high-quality pixel-art work...

...they have wonderful colour-schemes and shading; they look nostalgic because they have this "pixel-art" feel. I'm sure that that rock-texture from the mountains in the first picture you posted could be used in a 2D game without any problem.
Open Photoshop, convert those game screenshots into 'Indexed Color' images (256 colors), and then look at the pallete. Notice how all the colors are analogous and fit with eachother.
That wood-plank ground in the second picture makes it clear that these textures are hand-painted, and due to this these textures have that "anime background art", handmade quality:

Research on pixel-art coloring and color-schemes, and apply these principles to the hand-painted textures you'll create. That's the secret.
Henk Nieborg's gallery:
http://www.pixinspac...ery_pixels.html