There's a good soup I used to make as part of the "cabbage soup diet," that I
think would be just fine for paleo, using homemade stock such as that
mentioned by Richard rather than dried onion soup mix.  There could be chunks
of meat or bacon in the soup, too.  Once you have a base, all you do is add
tomatoes, cabbage, onions, and any other paleo vegetable -- I always use kale
in this soup, for instance.

Unless I'm missing something, there's no reason we couldn't eat lots and lots
of this soup, is there?

Caryl