Whoo! Sit down with a nice hot cup of tea. I've got a big answer. Pardon me, while I dust off my soapbox. ;)
DISCLAIMER #1: If you want to have children some day, then you should seek specific professional guidance (ie someone who deals specifically with reproductive health) when dealing with reproductive hormones. What you do today could have serious consequences years from now. That said, most women can correct years of hormonal imbalance in just a few cycles and still conceive.
DISCLAIMER #2: It's hard to say what's "normal" for someone doing paleo while on the pill, because I don't think being on the pill can be considered paleo. As people following a paleo diet, we're basically trying to regulate our hormones by eating quality food and getting quality sleep. Unless we have a real medical condition that requires prescribed hormones (the use of which usually tends to follow natural rhythms); we should not be messing with our body's natural monthly hormonal rhythms by using the pill.
So here's another situation where it's important to understand how the hormones are working and how they affect your body.
Abridged from "Taking Charge of Your Fertility":
Every cycle, under the influence of Follicle Stimulating Hormone (FSH), about two dozen eggs start to mature. Each egg is encased in a follicle. The follicles produce Estrogen. Estrogen is the hormone necessary for ovulation to occur. Eventually, when Estrogen reaches a threshold that is high enough, one eggs bursts out (ovulation!). This usually takes about two weeks from the beginning of menses but can take anywhere from 8 days to several months!
Following the release of the egg, the follicle that held the egg begins to release progesterone (typically for only 12 to 16 days). This is known as the Luteal Phase. Progesterone prevents the release of all other eggs and causes the uterine lining to thicken in prep for a fertilized egg. In 12 to 16 days, if a fertilized egg has not been implanted into the uterline lining, the follicle (corpus luteum) disintegrates and its flow of progesterone stops. The uterine lining begins to shed (menses) and the cycling begins again.
So that's the natural progression of things. But when you take a low-dose pill, it is pumping progesterone into your body for three weeks out of four, thus making your body think it's in the luteal phase (or think it's pregnant!). On the fourth week, when you stop the pill (or take the "other" pill), you stop the flow of progesterone. Your body responds by shedding the uterine lining (menses). Also in that placebo week, your body thinks, "Finally, we get to release an egg!" And it prepares to release an egg by upping the production of estrogen and follicle stimulating hormone (FSH). But after seven days, you start taking the progesterone again, before your body has released an egg! And your body is confused!
Here's a few potential situations given the information you've shared:
Ovulation (even though you're taking the pill, you could still be ovulating - ovulation is also associated with spotting, dull aches and cramps). Your body is still trying to up it's estrogen production, even while you're pumping it full of progesterone (especially on low dose!). And eventually it makes enough to ovulate (So, yes! You could get pregnant while on the pill!). Or...
Sudden drop in estrogen. Your body fights the progesterone with estrogen for a week and then gives up. This sudden drop in estrogen, often causes some mid-cycle spotting which is common and is nothing to be concerned about; but isn't often associated with cramps. Or...
Implantation (a fertilized egg has implanted into the uterine wall). You may actually have released an egg, and it may have burrowed into the uterine wall...! Or...
Any serious reproductive problem. Having a period every two weeks is not optimal and could signal reproductive problems in the future.
Because the "extra periods" seem to pop when you are being "strict paleo" I would suggest that it's likely #2 or #1. Your body is fighting back with proper estrogen levels then falling off. Or if the cramps really are like a normal period, I would suggest that your lose dose pill is possibly ineffective and you may be at risk of getting pregnant! Your hormones may just be trying to exercise their autonomy, as you said!
All other health concerns aside, I recommend getting off the pill and leveling out your hormones to really determine the health of your reproductive cycle, in consultation with your healthcare professional, of course!
Instead of using the pill, I highly recommend using Fertility Awareness Method. I've used fertility awareness method (FAM) with my husband for 4+ years and it's been effective thus far! You just have to get used to taking your temp every morning (or just during your fertile phase) and to checking your vaginal fluids. It's super easy! We just avoid sex when I'm fertile (or we use a condom). And we have sex when I'm not fertile. Takes the guess-work out of it!!
Get this book: Taking Charge of Your Fertility
And visit this website: Taking Charge of Your Fertility
The information in the book will blow your mind. I was sooo mad that I hadn't been taught any of the information found therein while I was in biology class or sex ed in high school. We should all know this stuff!! And if you're serious about ensuring that you're regulating all your hormones effectively (via the paleo diet), then you should seriously consider, allowing all your hormones to do their thing naturally!
And please... GET OFF THE PILL!!
P.S. If you were consume soy products and have recently stopped because of paleo, you're getting a much lower dose of estrogen than you were previously. Something to consider.