1. Potentially you could take the quickest solution and fill them in with black because it wouldn't look out of place. I'd imagine the pillars would be casting a black shadow to the right side anyway based on other backgrounds in the game.
2. Something I thought of, which isn't exactly true to the source material but, what if you darken the backgrounds slightly by dropping the brightness? You could always keep both versions of the backgrounds available if someone wanted to specifically use the original or edited versions. I can play around with them if you'd like and see if we can find a good mid-ground.
3. If the problem is the tileset blending in too much with the background, then maybe 2 might be the way to go? Otherwise I think it looks fine.
EDIT:
Here's a quick sample I did (default, -35% Brightness -35% Contrast, -50% Brightness -50% Contrast)
I think this is similar to what they did with some of the Mario Maker backgrounds for SMB1 and SMB3. Let me know your thoughts!
