Go back to the doctor, get other bloodwork done. Women are prone to a couple of different endocrine issues that are related to weight gain - namely PCOS and hypothyroidism. Both are very often under- or misdiagnosed. For PCOS, you need at least the following bloodwork - DHEAS, fasting insulin, and fasting glucose. Ideally, she should also get free testosterone levels checked, as well. For hypothyroidism, TSH testing isn't enough, get the free T3 and T4 tests done, as well. At the very least, this will rule out medical issues.
Hammer down on the food tracking. That she's eating Paleo and tracking is great, but she can probably do better. After all, it doesn't matter if she's eating chicken and broccoli all day, if she's eating too much, she's going to gain. At the very least, measure everything. Even better - weigh it. This gets her the most accurate numbers she can get. Also, don't substitute. If the food item isn't in there, or doesn't match what is on the package or in a cross-referenced source, then either update the entry or add a new one.
Get a heart rate monitor. MyFitnessPal is notorious for wild estimates for calorie burn. Get a heart rate monitor and use it for any and all exercise. Use its numbers over MFP's.
Eat the calories back. If she's using MFP's system for calculating calories, and her workouts aren't figured into the calculation, then follow how MFP does it and when she exercises, she eats more to account for them. MFP builds in the deficit when you configure it, exercise above and beyond the configured value is gravy.
Double-check other medications. Is she on birth control? Most hormonal birth controls are known to cause weight issues, and Depo Provera is often the worst offender. Does she take any other medications? Check them for weight issues and see if they can either be phased out (with doctor's supervision) or changed to something that doesn't cause weight issues.
Go back to Paleo basics. As, Humans are not broken puts it you might be getting too good at Paleo. If the SAD-style "treats" have worked their way back in, though technically Paleo, they might be causing issues (particularly if they have some kind of sweetener in them). Do a Whole30 to get back to the basics and force a habit change. At the very least, go through your typical meals and cut the chaff and stick to the powerhouse foods.
Tweak macros. Paleo isn't necessarily low-carb/high-fat, and some people do better on low carb, while others do better on higher carb. This will partially depend on what the aforementioned bloodwork comes back with, though. If she shows signs of insulin resistance, then lower carb will probably be her best option. If she doesn't, then she's more free to try increasing the carbs (depending on where she's at now).
Change up the workout routine. It's possible that the intensity of Crossfit, plus the spinning classes are too much and too intense. Try dropping one and do some dedicated power lifting or strength-oriented body weight training, or just drop one for something less intense altogether. Mark Sisson puts it elegantly - "move frequently at a slow pace." You don't need to power through an hour of spinning at top speed, when an hour walk or leisurely bike ride will suffice and won't cause your body as much stress (and thus, cortisol production).
Be patient. It took 2 years to gain those 15 pounds. They're not going to come off overnight. Give any changes at least a month, before giving up on them. And if she's anything close to normal weight, it might take longer to see the scale move. Fifteen pounds in 2 years is just over half a pound a month. Don't expect it to come off much faster.
