I've lost weight on a paleo diet by eating lean animal protein (fish,
skinless poultry, very lean red meat, and whole eggs) with much larger
volumes of non-starchy vegetables and fruits, and using very small amounts
of added fats/oils.  You can eat a lot of food this way, without consuming
excessive calories. For some this leads to greater satiety. This way of
eating has worked for me, even with small amounts of bananas or sweet
potatoes at some meals and on some days.  Eating a very high meat and fat
diet with little or no produce can lead to consumption of excess calories,
at or above maintenance needs, particularly for women, who have lower basal
metabolic needs than men.

Rachel