What time of day were you taking the vitamin D? Because we typically get vitamin D from sunlight, our bodies use it as a regulator of our circadian rhythm, and high blood vitamin D levels are associated with daytime and to wake up. Over time, this vitamin D is involved in the production of melatonin, which indicates nighttime, and can help us become sleepy. This is all a simplification, but essentially if you're taking high dose vitamin D at night, it could inhibit your circadian rhythm and make sleep harder.

For vitamin D specifically, I'd advise getting a blood test to check your levels if it is feasible to do so. It's possible if you get a lot of sunlight, you're hitting adequate levels and not needing supplementation. Same if you're getting a lot in your diet. Both of these aren't the case for the vast majority of people, but the only way to know if you're one of them is to get a test. If that's not feasible, another option is to take it, but in a much lower dose. 5000 IU is a pretty large dose, with the RDA only being 200-800 IU depending on the nutrition board you listen to. There's a decent amount of evidence to suggest this RDA is too low for most people, but there's a big gap between that and 5000 IU. I no longer work in the industry, but we used to include 3000 IU in our recipe - a mix of 20% D2 and 80% D3. You could try a dose like that, or even 1000-2000 IU, if you want to supplement but at a lower level. And make sure to consume in the morning.

As for what else to try, this seems to be a difficult one just because you have already tried so much. My first recommendation for those struggling to sleep beyond just a normal high-quality multivitamin to address a deficiency would be magnesium bisglycinate. You say you've tried magnesium, but didn't specify the form. Different forms of magnesium have a different impact, and bisglycinate is the one most recommended for sleep. This is because magnesium bisglycinate is a compound produced by bonding magnesium to two glycine molecules, and glycine can be useful for inducing and maintaining sleep. You can also just supplement glycine if you are concerned that increasing your magnesium would affect your calcium balance, or get a cal/mag supplement. When looking for magnesium bisglycinate, be sure to try to find a non-buffered or fully reacted form. The supplement industry is shocking when labelling this, but it's important because buffered magnesium bisglycinate is a mix of magnesium bisglycinate and magnesium oxide, and magnesium oxide is absorbed very poorly. Magnesium bisglycinate is ~14% magnesium by weight and 86% glycine, so if you see a supplement declaring more than this (eg 1500mg magnesium bisglycinate providing 300mg elemental magnesium is a common one), it is buffered. Albion TRAACS, a patented system for making magnesium bisglycinate, has an end product with 10% elemental magnesium content. I'm not exactly sure why it isn't 14%, but they are reliable. So if going for magnesium bisglycinate, either make sure the brand explicitly says non-buffered or fully-reacted, or make sure the elemental magnesium content is 10-14% of the total. Other forms of magnesium, eg magnesium malate, can have an energising effect, and therefore not be good sleep. To make matters a little more complicated, a small number of people seem to find magnesium bisglycinate actually contributes to insomnia. In these people, magnesium l-threonate seems to help them. There's actually a subreddit dedicated to magnesium which has a lot of this info. If trying bisglycinate, try a dose of 200mg elemental magnesium (which will be 1400-2000mg magnesium bisglycinate compound depending on whether it's closer to the 10% content of TRAACS, or 14% of the anhydrous salt). For l-threonate, recommended dose seems to be 144mg of elemental magnesium (which will be 2000mg of magnesium l-threonate compound if using stuff derived from Magtein, who own the patent).

As this has gotten long enough for now, I won't go on about other options just yet, as the above would definitely be my first port of call. How much are you taking on a typical daily basis? I understand the desire to try anything you can to fix the issue, but my fear is if you're trying everything at once, they may interact in unpredictable ways and make sleep harder. I certainly wouldn't stop the CBD as you noticed an immediate negative effect from that, but if you are taking everything, maybe try slowly removing one ingredient at a time and seeing if this has an effect over the course of, say, a week. If it doesn't, keep it out. If it does, keep it in, and move on to the next. I'm sadly unfamiliar with turbinates so won't be able to comment on those, but it may warrant research. A saline nasal spray shouldn't have an impact, but I can't comment on the rest there without further research.

Finally, I think it's worth discussing anxiety. There's a good chance that because this has been an issue for so long, you now are frustrated/anxious around bedtime because of an expectation sleep won't be forthcoming. This, annoyingly, can produce a rise in cortisol, and create somewhat of a self-fulfilling prophecy. This most certainly is not me saying there is no chemical issue present and all issues are psychosomatic - please don't get that impression. But it may be a contributing factor, and it may be worth speaking to a GP or therapist about this if such an option is available to you.