If your trigs have gone up it means you're eating more carbs that you should. Trigs are directly related to carb intake and have a much higher correlation to CV disease than total or LDL cholesterol. It's not eggs that are your problem. Dial back on sugars (even "natural" sugars supposedly permitted on Paleo) and if you're eating lots of starchy veg or fruit then cut back.
It is untrue that eating cholesterol increases your cholesterol. Take some time to read this entire series:
This is a 10 part series (part 10 isn't up yet), and highly technical. If it's too long, don't want to read it, there's one nugget there - we only absorb 300-500mg (that's less than half a gram) of external unesterified cholesterol from food. Our cholesterol levels are very tightly controlled, and you could eat 500 egg yolks a day and not make much difference to your cholesterol levels. Further, the whole eating saturated fat and or cholesterol will cause your heart to burst is pure marketing myth to get you to buy hydrogenized industrial seed oils, which are infact harmful to cardio-vascular health.
Cholesterol is also used as part of the immune system, you might have some infection you're fighting off, or something is highly inflammatory in your lifestyle/diet. You could be gaining weight for many reasons: insufficient/interrupted sleep, too many carbs, lowered thyroid function, too much stress, incorrect exercise (i.e. chronic cardio followed by binging because you thought you've earned it from the exercise.)
You obviously eat more than you burn, maybe thinking what you eat is healthy causes you to eat more, consciously or not. Other than that, 2 things come to my mind:
1) Thyroid hormone problems, which may be caused by giving up iodised salt and not including enough iodine or maybe other factors as well in the diet. Thyroid hormonal activity regulates ldl-receptor activity.
2) You are one of the people that respond to dietary cholesterol with an increase in cholesterol numbers, but remember that this alone does not explain any worsening of the ratios and may in fact be protective as well because when lipoproteins carry more cholesterol, they are less likely to oxidize.
Dietary cholesterol only contributes to approx 15% of blood cholesterol level - the body is way more complicated in how it metabolises dietary fat / cholesterol. So eating eggs and other healthy fat foods should not massively impact your cholesterol. Cholesterol is also not the villain current medical guidelines make it out to be - it is a marker to show there is an issue but it is not the cause of heart disease etc. It's like turning up at a fire and blaming the firemen for the fire... Quite often inflammation can be the cause for a lot of the modern conditions and therefore the cause for higher cholesterol. What causes inflammation - diet (high carb, sugar, processed food diets), infections etc.
You also do not mention what cholesterol number is up. Total cholesterol is meaningless - if LDL is up that may be a concern but it depends on your HDL / Triglyceride numbers and ratio's - for example if Triglycerides are low (<50) and HDL is high (>50) then LDL number is likely to consist of the large 'fluffy' LDL which is considered benign. If Trigs are high and HDL is low and LDL is high then that implies that the LDL is the small dense LDL which is the dangerous kind. I recommend Jimmy Moore's "Cholesterol Clarity" book to help clarify a lot of these types of questions.
I don't know what your intake is or what your movement is -- let alone history :) Here's mine:
I had high cholesterol (total and the bad with low good) since my teens, when they discovered it. My family ALL has CAD and manage to drop dead from related acute issues (stroke, heart attacks, etc.).
I'm the poster child for paleo in many ways:
I was put on a vegetarian diet for almost 20 years (lots of whole grains and legumes!!) and told to do lots of cardio. I did that and over the years, my situation grew worse. When I was at last told that I had to go on RXs, I asked my GP (thank goodness she understood inflammation) if there wasn't anything else that I could do rather than go on meds at age 39? She put me on an elimination diet (basically the autoimmune protocol) and within 8 weeks of no legumes, no grains (eating same freggies and fats), I not only had the best blood panels of my life but had blood panels healthy people would long for! If you're not familiar with autoimmune protocol, get googling. It's great for people with autoimmune -- obviously -- but if you're got cholesterol issues, I guarantee you'll benefit from it.
Inflammation is a beast and legumes and grains are its fodder.
When you say you're eating paleo, it's not eating 2-4 eggs a day (I do and I'm 5'2", female and work a desk job) or red meat (eat that daily, too) alone. It's more about making sure you're getting COMPLETELY rid of things, too, like all grains, faux-grain (amaranth, quinoa) and dairy. If I have one serving of dairy, my skin problem explodes. None? What skin issue? Inflammation applies to our insides, as well.
I had doctor supervision for almost 2 years (after results of 8 weeks, my doctor was GIDDY and we worked on getting rid of other foods that gave me problems). After a few months, I 'found' paleo (similar to AIP) and that has been a lot of fun, adding ideas. Don't give up right away.
Subsequent years of blood panels have shown that I'm still within healthy levels yet never had been before, even as a kid! It's crazy! I'm in my 40s. Does it take work avoiding hummus and ice cream? Yes, yes it does. But at least I can have lots of eggs :)
To help lower cholesterol:
Eat meat sparingly(steer clear of meats like liver, brain, and kidneys)
Reduce salt intake
Try to bake, steam, broil, etc instead of frying.
For weight loss:
For some people, 2 Tbsp Apple cider vinegar+16oz of water works(it didn't work for me), or a cup of bitter dandelion root tea a day can help you lose weight. Plus they both are good detoxing drinks.
Go to sleep at a time you don't normally sleep or practice fasting to loose the weight.
Like Matt said. You're eating too much. Don't eat if you aren't hungry. Simple.
that too Matt11; egg whites should not increase your cholesterol - that's a function of eating too many yolks; also change your protein balance to increase fish and chicken, decreasing red meats; still drinking beer?? it's grain based...... exercising? lots of other questions before your question can be answered