I'm a small boned, short guy. I can eat fat calories all day long and not gain a single fat cell on my waist so I wouldn't concern yourself so much with the number of fat calories than the type of fat represented in that calorie. All fats are not created equal.
Paleo emphasizes the Omega 3 fats from (and this is strict) wild caught fish and seafood. You can eat salmon, tuna, any kind of fish. You can also derive Omega 3 fats from wild caught shrimp. As for mollusks, you can buy them farm raised since they only survive on zoo plankton regardless of their environment. They cannot survive on Omega-6 drenched feeds high in corn oil and soybean oil. So you can eat clams, oysters, mussels and scallops even if they are farm raised in a controlled environment. The other type of fat is
Your saturated fat should come from (and this is also stricta worthwhile Paleo ideal) from grass-fed animals like cows, pigs, chicken and turkey. Organic DOES NOT MEAN grass-fed. Organic just means the feed is organic soybean oil and organic corn oil-based, BOTH dangerous omega 6 fats. Eggs from grass fed chicks are another option for saturated fats and cholesterol. Free-range DOES NOT MEAN the eggs were laid by grass-fed chickens. It means the agribusiness bad guys sprinkle Omega-6 feeds on an open barren pasture.
Think more about where you shop and that will help you get what you need faster than if you walk into a supermarket and attempt to piece together a good meal plan. If you shop at the right places like local farmer's markets you can find more of the food you need much faster and without the hassle involved with investigating confusing food labels.
Veggies are the most preferred form of carbs. I think fruits are fine as well.
I've been leaning towards buying beef tallow (cow fat) and lard (pig fat) to use to saute veggies and use for stir-fried shrimp and pork. You can fry sweet potatoes in beef tallow. It makes a great side dish for your meats. In your stir fry vary herbs, spices and sauces using lemons, limes, oranges, different kinds of berries and variations of them all.
Stir fry is a preferred method of cooking because you retain a greater proportion of the vitamins, minerals and amino acids in these foods.