Sudden thought: Is it possible to steal an unfinished Shakturi PK by killing the constructor, then completing it yourself? Because if that's the case then the galaxy will very soon have a whole ****load less bugs to squash.
If I recall correctly, the planet killers that the Shakturi construct in the Ancient Galaxy scenario are actually owned by the Shakturi from the time they spawn on the map. If you want to steal them, you're going to have to use boarding pods (I think the boarding defense of a completed planet killer is something like 800; you'll probably need a lot of pods), as your construction ships cannot be assigned to work on projects owned by another faction (the project needs to be either neutral or owned by your empire). Good news is that incomplete vessels and stations are valid capture targets.
Be advised that a completed planet killer (or a planet killer with all of its hab modules completed) has a boarding defense of around 800. You'll probably need a lot of assault pods.
Loading up on Nuclear Devastators doesn't seem to DO ANYTHING when I tell ships to attack a planet...
How many Nuclear Devastators? Because just a handful per ship isn't going to cut it; even a fully-upgraded Nuclear Devastator is only killing 1.33 million per second at normal game speed (8 million per shot, with one shot every six seconds), and even if the planet's population isn't growing it'll take a very long time to kill a world with a decently large population at that rate. Note that to reduce the population of a target world, a bombardment force has to outpace the natural population growth rate of the planetary population or it has to damage the planet's quality to the point that the planet's population cannot continue to grow quickly enough to keep up with the bombardment (either due to the population being capped due to planet quality damage, or due to the population growth rate being reduced by the lower planet quality).
When I bother with planetary bombardment, I bring multiple dedicated bombardment ships, and those ships will have at least 10 (probably more like 20-30, and later in the game potentially upwards of 50) bombardment weapons. If you want to kill a planet quickly, you're looking at bringing 100+ bombardment weapons to the party (even 100 fully-upgraded Shaktur FireStorm torpedoes, the best bombardment weapons in the game short of a planet killer, will take on the order of a minute at normal game speed to kill off a planetary population of 20 billion, even if the ships are undisturbed and the planet lacks defenses against bombardment).
Also, be absolutely certain that the target planet does not have a planetary shield generator; no bombardment weapon short of the Super Laser can touch a planet protected thusly, and you will have to at least land special forces on the planet before you can bombard it (in the hopes that the special forces will destroy the shield generator). A planet protected by a Planetary Shield Generator has a sort of blue-green glow around it that other planets lack; alternatively, you could look at what facilities are present.
I know the Shakturi had 4 PKs building when I scouted them earlier, do they build more after you destroy the initial bunch or not?
If you destroy the planet killers before they're completed, the Shakturi will begin building replacements. I don't recall if they replace them if destroyed after completion, however.