We present 10 new Spitzer detections of fullerenes in Magellanic Cloud Planetary Nebulae, including the first extragalactic detections of the C70 molecule. These new fullerene detections together with the most recent laboratory data permit us to report an accurate determination of the C60 and C70 abundances in space. Also, we report evidence for the possible detection of planar C24 in some of our fullerene sources, as indicated by the detection of very unusual emission features coincident with the strongest transitions of this molecule at ~6.6, 9.8, and 20 μm. The infrared spectra display a complex mix of aliphatic and aromatic species such as hydrogenated amorphous carbon grains (HACs), polycyclic aromatic hydrocarbon clusters, fullerenes, and small dehydrogenated carbon clusters (possible planar C24). The coexistence of such a variety of molecular species supports the idea that fullerenes are formed from the decomposition of HACs. We propose that fullerenes are formed from the destruction of HACs, possibly as a consequence of shocks driven by the fast stellar winds, which can sometimes be very strong in transition sources and young planetary nebulae (PNe). This is supported by the fact that many of our fullerene-detected PNe show altered [Ne III]/[Ne II] ratios suggestive of shocks as well as P-Cygni profiles in their UV lines indicative of recently enhanced mass loss.