I was lucky and I had a backup of my game from yesterday, when I'd just gotten into the space stage and had only contacted 1 or 2 other empires. This time, I was allowed to start the "go to war" mission with a nearby empire. It looks like the only time you're likely to be able to start this mission is very near the beginning of the space stage.
Of course, this is a really bad time to go to war - you will be weak and it's a distraction you don't need. Nevertheless, you have no choice if you want to complete this mission. What I recommend you do is quickly make an ally - complete the "make an ally" mission from your homeworld - and then start the "go to war" mission. All the other homeworld missions will still be available later. Then, leave the "go to war" mission simmering away. You won't actually declare war on the empire you're meant to go to war with until you attack them. Work at building up a few colonies, and building up about 400,000 Sporebucks. Then, attack the empire you're meant to attack. This will give you the warmonger badge, and you can go straight back to your home colony and buy mini bomb. You're gonna NEED mini bomb to complete this mission.
Once you've done this, begin a process of going to your ally, picking up a ship from them for your fleet, going to the planet your mission tells you to attack, and bombing its cities. You'll probably have to do this several times until you destroy all cities (or cause them all to surrender, whichever you choose). You then finally complete the "go to war" mission, and can get on with all the other ones.
As I said, this is a headache, and is only for the perfectionists (like me) who want to complete every single homeworld mission available. :-)