You over-simplify.
There are two problems:
1. Kirby 3D Classic's background tiles has 4 different depths (or 5 if you consider the clouds with 2 depths). The most important problem is that the original NES doesn't store this information about which tile is at which depth. So the only way to do this is to mark the depths of each tile by-hand outside of the game.
2. To generate two images for the left and right eye, you need to vary the positions of tiles at each depth images slightly (parallax). That means that at same areas, some background tiles will peak through due to parallax. In reality, you should have up to 4 layers of tiles, one for each depth layer. Obviously the level design needs to pick the correct background tiles for each layer, otherwise, what shows through due to parallax will not look right. Again, the NES game has only ever stored 1 tile per square in its games.
So yea, it's impossible because it cannot be done within an emulator, because of the lack of depth information in the original games.
But yes it can be done, only if a developer re-develop the games individually from its original source, in which case the task for the developer is to design 4 separate layers of tiles, and place the correct tiles in the correct layer, then display those layers for the left/right eye (shifted by a bit for each eye).