I think its a bad sign that you wake up hungry. Since we paleos typically run on fat rather than carbs, our hunger is less acute and more stable because our blood sugar doesn't go crazy. You, like me, might be higher carb than average, since you say you're only 80% paleo. So, I suggest:

(1) Only eat carbs (starches, unprocessed) for breakfast or post workout.

My brother's crossfit instructor eats sweet potato for breakfast. And Stephen Guyenet eats potatoes in the morning and mid-day as well. That, basically, ought to give you carb-based energy for the day, and let you fall into a natural state of ketosis at night.

Relatedly, some people find that going too low carb affects their sleep negatively. So, you might just be too low. If this is the case, try:

(2) Incorporating more carbs into your diet in general, especially sweet potato and white rice.

Finally, Seth Roberts finds that if he eats breakfast too soon after waking up, then he tends to wake up earlier the following day or days. This is the response of a food expectation system. Your issue is both different (falling asleep v waking up early) yet similar (mistimed hunger). So, consider:

(3) Skipping or delaying breakfasts for several days and tracking the effects.

Finally, following the Jaminets and others from similar posts on this site, consider supplementation:

(4) ZMA (zinc & magnesium) and melatonin are natural supplements that assist falling asleep. Magnesium is a muscle relaxant, and melatonin helps get the falling asleep process under way, via the hormones that blue light suppress (if I recall correctly)

Hope these ideas for self experimentation prove fruitful - good luck

I have found that in the 7-10 days leading up to my menstrual cycle that I sometimes suffer insomnia. Can you note any correlation? I know we are all different in that respect. I know sometimes for me it is worse some months than others and I consider myself to have a "normal" cycle.

Sometimes if I am low on sleep for a few days, my body gets into this overdrive mode where I don't sleep at all. This can also happen if I am stressed about something or am eating a poor diet. This goes on for about 7-8 days and then suddenly I crash and get extra sleep for 2-3 days.

Lack of exercise destroys my sleep schedule too. If I go 2-3 days without some kind of exercise, it's possible to fall and stay asleep. Then it can take 2-3 days to get back to normal. So moderate exercise for me every day or every other day is really the only way to go. If I have real blowout exercise and am sore or injured and can't get any for a few days, it puts me back into a bad sleep cycle.

All of that said, all of this is way better with a strict Paleo diet. I have never slept so well for so many weeks in a row.

You might try a standing desk or strong lights upon waking which Seth Roberts found worked for him