Under the "Start Here" button at the top of the page is a link to Griff's Cholesterol Primer. That should get you going a bit better on what you need to know about statins and paleo and cholesterol.
Second, remember that Primal and paleo are both plant-based diets. You should be eating a lot of leafy greens and other vegetables, as well as some fruit. You should get sufficient fiber from these things without having to supplement any, though you may experience some side effects as your body transitions over.