5-staring every mission can be quite a daunting task, given that a lot of the mission starts are very far from the mark. There a few weapons and accessories you'll want to get before attempting this, especially the higher ranked ones.
Malboro Wand (weapon - Vanille) - This wand is upgraded from the Belladona Wand (bought from Plautus' Workshop). It gives Improved Debuffing II which really helps against tougher enemies that are susceptible to Death.
Aurora Scarf (accessory) - This starts you off with a full ATB gauge at the start of a battle, giving you the jump on your enemy. It is the upgraded version of the Whistlewind Scarf (The Moogleworks).
Sprint Shoes (accessory) - Having these gives you auto-haste at the beginning of a battle. To get them, upgrade a Tetradic Crown until it has a star by it's name. Dismantle the crown and you'll get Hermes Sandles. Upgrade them to tier 2 and you'll get your Sprint Shoes.
(Another way to get the Sprint Shoes is to fully upgrade the Tetradic Tiara, then dismantle it.)
Gold Watch (accessory) - This is probably the most valuable accessory when it comes to getting 5 stars. It will increase the target time of your fights, making it easier to get the 5. To obtain it, you must complete mission 64. Here's a video, if you're having trouble.