I'd guess the most efficient way to have stars would be to include them in the planet image. It would be an overall background image instead of just the planet, that way the stars and whatever else you have in the background all move together (breaking them into separate elements, however, would cause a lot of slow down, I'd think). Are you using SPRITECOLLIDE for the planet? I'm guessing that's why you don't have any stars.
Tireas, the speed of yours might have to do with the size of the superstar.gif. It's 208k, you should be able to compress it to a fraction of that, even if you have to convert it to a jpg or a png.