Solenoid capacitor circuit for paintball gun
I am not sure how you came up with your Joules requirement but your capacitor has about 0.275 joules of energy at 9 volts (W=0.5*C*V2). And that assumes you take the cap down to 0 volts which will not be the case. If you care to elaborate on your Joule calculation, perhaps this could be refined.

The ESR (Effective Series Resistance) of the cap will also play a role as it effectively converts some of the capacitor's energy to heat during the discharge cycle. It also slows the charge time of the cap. And it slows the fire time of the solenoid. Select a capacitor with the lowest possible ESR to minimize these effects.

The RDSon of the FETs are important as they too will work in the same way as the ESR of the cap. Choose FETs with low RDSon.

The timing sequence should be to have both FETs off initially. Then turn on the left FET to charge the cap. When you want to fire, turn off the left FET and then turn on the right FET. If you have both FETs on to fire, you will not get the desired high energy effect from the cap.