Maybe 'paleo' means 'very old'.
If it just meant 'old' we could we could go back fifty years: prawn cocktail, ham and pineapple chunks on cocktail sticks stuck in a grapefruit to look like a hedgehog, black forest gateau ... butterscotch angel delight ...