This is the most time consuming achievement in the game. After completing the required campaigns, you will most likely still need to grind around 2500 kills. The fastest method I found for grinding is to keep replaying Level 16 of the Lost Levels. While this level only has 30 enemies they spawn very fast and can all be wiped out in about 30-40 seconds. As soon as the level begins, migrate to the top left corner (by the moon) and shoot all the enemies as they mob you. With this method, you can accumulate roughly 2000 to 2500 kills per hour.
You can check your progress towards 5000 kills upon completion of any level in the statistics screen.