Greetings, y'all.

The way I see it, you have at least three games running here:

The first game is the contest between plants themselves, striving for
advantage by getting their seeds spread and fertilized by packaging them in
enticing, non-toxic tissue to encourage animals to eat them. That's a
win-win kind of game, and I think most here agree that's pretty paleo.
(assuming that there was enough time elapsed for that fruit's unique
proteins to be adapted to by the immune system).

The second game is the contest between plants and insects/herbivores, where
the plants create a range of poisons and nasty tasting/smelling compounds
which they lay down in the photosynthesizing or structural components of the
plant to deter predation. That would almost certainly include most nuts and
non-fruit-surrounded seeds, since they're designed to be spread mostly by
physical forces. Given the size of non-insect herbivores and omnivores, the
dose of such poisons would rarely be fatal (or even particularly acute), and
hence, they'd have the opportunity to adapt through gut and immune system
changes to deal with constant low-dose exposures to plant poisons. An
interesting twist on *that* game is that the advent of domesticated
vegetable/nut crops probably has let us breed plants with less toxins and
alkaloids. In other words, veggies or nuts that we've long been exposed to
would also be rendered relatively safe (and paleo) because of our
adaptations to the poisons involved.

The third game is the predator/prey relationship among herbivores,
carnivores, and omnivores. From what I remember in my studies, many dynamics
argue against the use of a tissue-poisoning strategy in animals (including
most insects).  Making toxins and keeping them separated away from tissues
is a fairly energy intensive activity, and rarely makes a good strategy for
animals compared to the wide range of alternate strategies they have
available. It would be largely ineffective against insect populations, for
example, which evolve too quickly for the larger, slower
smaller-population-size animals to compete with that way. Any poison a cow
could generate and saturate its tissues with, would quickly be countered by
insect evolution, well within the lifetime of that very same mutant animal.
Plus, it's not a good thermodynamic trade: the energy needed to make and
contain the poison is more than that needed to replace the tissue eaten by
an insect one billionth of your mass. Also, even if an herbivore mutated to
have such poisoned tissues, predation on larger animals is rarely of the
sort that it is with plants, such as blights that wipe out all but a few
nasty tasting poisonous mutants, spurring directed evolution of that trait.
In other words, the thermodynamically expensive trait probably wouldn't be
maintained. The upthrust of this is, in eating animal flesh, you're
essentially eating non-poisoned tissues of close physiological composition
to your own, which should be quite paleo.

My two cents,

Ken Green