healthy oils (olive, flax seed, coconut, grapeseed, etc.), fruits, and nuts
and seeds (no peanuts or cashews).

Olive oil and perhaps coconut oil would be acceptable as they are not
expeller pressed out of seeds. Both these oils should be virgin. No oils
that are pressed out of seeds could be paleo. All grains and seeds are not
paleo. All seeds have the self protective qualities that make them
unsuitable as human food.

Most people that eat paleo cheat with this or that food. Some of us call
that by its right name and some of us insist on calling it paleo just
because we like it.

Personally I believe that it is more likely that paleo people ate saturated
fat from meat than butter or flax seed or rape seed oil. On the other hand,
people of European descent are better adapted to butter than to rape seed
that only used to be oil for lamps. Flax seed used to be a remedy for
constipation and it worked because the body immediately recognized it as a
"no-food" and got rid of it as fast as possible. Neither rape seed nor flax
oil are edible without heavy processing; something that is generally not
considered paleo.

My personal advice is to change a little at a time. Some people change from
one day to another but I think you have to be a rather good cook and know a
lot about food to do that. Serve yourself less of non-paleo foods and serve
it more seldom. Eat more of what you alreade like. Try a new vegetable each
week. Eat many different vegetables every day. Don't rely too much on fruit
or on nuts. Start with avoiding the really bad things, dairy and cereals!

Good luck!
Eva