Shock caused by impacts can convert carbonaceous material to diamond. During this transition, new materials can form that depend on the structure of the starting carbonaceous materials and the shock conditions. Here we report the discovery of cage-like nanostructured carbonaceous materials, including carbon nano-onions and bucky-diamonds, formed through extraterrestrial impacts in the Gujba (CBa) meteorite. The nano-onions are fullerene-type materials and range from 5 to 20 nm; the majority shows a graphitic core-shell structure, and some are characterized by fully curved, onion-like graphitic shells. The core is either filled with carbonaceous material or empty. We show the first, natural, 4 nm sized bucky-diamond, which is a type of carbon nano-onion consisting of multilayer graphitic shells surrounding a diamond core. We propose that the nano-onions formed during shock metamorphism, either the shock or the release wave, of the pre-existing primitive carbonaceous material that included nanodiamonds, poorly ordered graphitic material, and amorphous carbonaceous nanospheres. Bucky-diamonds could have formed either through the high-pressure transformation of nano-onions, or as an intermediate material in the high-temperature transformation of nanodiamond to nano-onion. Impact processing of planetary materials was and is a common process in our solar system, and by extension, throughout extrasolar planetary bodies. Together with our previous discovery of interstratified graphite-diamond in Gujba, our new findings extend the range of nano-structured carbonaceous materials formed in nature. Shock-formed nano-onions and bucky-diamonds are fullerene-type structures, and as such they could contribute to the astronomical 217.5 nm absorption feature.