If you are a little bit used to OpenGL, I think it's the easiest and most performant (in the last few days, I looked at the NeHe OpenGL tutorials, and at the moment I am experimenting a little... I think one learns the basics quite fast.)
Otherwise Phreak's method is probably not bad, either. Alternatively, you could use a sf::Shape to draw very small objects. The problem is, if your star has got a texture, you have to take a sprite or use OpenGL.