It can be done! There are lots of painted buttercream cakes out there. I have seen the Starry Night done before in BC.
Make sure your base icing is ice cold so it's nice and firm. Are you painting with food coloring or thinned BC? If it were me I would use the thinned BC since it will blend a bit better, and give it a chunkier appearance like a real oil painting.
You know the painting. Just make yourself a thinned BC palette of blues, greens, and black. You'll also need yellow and orange. Just go to town! You might want to print a rough outline on some paper and use a toothpick to trace the design into the base coat of BC. Get a soft paint brush and use a light touch. If you feel the base coat is giving way, or you're picking up the base icing on the brush, refrigerate it again.