Youre right about paleo.. people eat plenty of carbs.. theyre just fruits and vegetables.. I kinda like paleo even though im not a big protein guy...
one day I said Im going to eat like jack lalanne.. so i basically cut out all sweets and sugars, starches like potatoes and corn (except corn flakes), no white flour or pastas or breads and no fast food, pizza, etc. I usually lost between 3-4lbs a week doing that.