I can tell you with full assurance that breathing is a big issue with you, and life in general will be much better for you when you get it under control. It will be especially helpful to you in scuba.
You really should not have to exhale through your nose while in scuba. You should be able to have long, slow, controlled breaths through the mouth, only using the nose to exhale when equalizing the mask (which takes so little you should not even realize you are doing it) and to clear water out of the mask.
If you are not breathing--especially exhaling--properly, whether on scuba or while driving down the road at 70 mph, you bring on a host of problems. Most importantly, you get a slow and steady buildup of carbon dioxide in your system. When you hold your breath long enough to get that panicky feeling that you need to breathe, that feeling is not generated by a lack of oxygen, it is generated by a buildup of carbon dioxide. When carbon dioxide begins to build up, you begin to feel panic. When you begin to feel panic, your breathing gets shallower. When your breathing gets shallower, more carbon dioxide builds up, and you feel more panic. That is called the panic cycle.
Carbon dioxide buildup during dives will also cause headaches.
Work on long and full exhales through the mouth while you dive. Make sure you empty your lungs from time to time. Everything will be much better for you.