The EMT-P to PA to DO route is definitely not a shortcut. In fact, it is more like the scenic route...except with more debt.
Also, I think the PA to DO bridge that is offered is only for people interested in entering primary care. So if you are interested in EM, surgery, gas, etc. throw those ideas out the window.
NP is not a bad choice, but be aware you have to specialize as an NP. You will have to go through with NP school and then essentially get boarded as an FNP, ACNP, PNP, etc. Nurse Prac doesn't have the flexibility that PA does, IMHO.
As a PA, you can choose to do a residency, and it seems like more and more groups are giving preference to PAs who have done a residency in whatever specialty they are seeking to pursue, however, it is still rare to see a PA position posted where part of the minimum requirements includes a residency. As FLDoc said, it isn't uncommon to see PAs change groups, or even specialties. NPs can change groups fairly easily, but changing specialty is a whole other matter, at least in Texas. It may be different elsewhere.
The last thing I will say about the NP route is that I have never really held NPs who went straight through nursing school and immediately entered an NP program in very high regard. I always felt like a nurse should do at least a few years at the bedside before he or she pursued NP school. That's just a personal pet peeve of mine...for whatever reason.
None of the routes are easy, and they all have drawbacks. I have had more than a few physicians tell me that they would have chosen a different route if they could turn back the clock. I attribute a lot of that to the fact that times are changing. Some people view this as a bad thing...I look at it more from the perspective of being able to actually get in on the ground floor of the changing face of healthcare, and hopefully contribute in a positive manner.
My father in law is a physician, and has been for over 30 years. He does seem pretty miserable right now, but it is a result of multiple things happening at once. He is not very tech savvy, and let's face it, in today's world, if you can't work a computer well, your day is just going to suck. He has been set in his ways for a very long time, and the changes are coming faster and faster.
This rationalization may just be my way of fooling myself into thinking it will be different for me when I am done with medical school, but I certainly hope not. Many of the complaints that the physicians have the mid levels still have to deal with.
I will also say that I have seen more than one physician who would not change what they do for all the whiskey in Ireland, and their level of satisfaction overflows into their patient care. They are some of the happiest and most amazing people I have ever met (probably because they are out of medical school...)
My last word of caution would be to remain mindful of how you come to terms with things in your head. Going into PA school thinking that it is the most expedient way to get to the level of practice you want, without the difficulty and commitment that medical school requires opens you to the possibility of disappointment. It may happen that you find yourself in 6 years as a PA, relatively happy, but wishing you could do more. This might not occur to you now because there is so much more you can do as a PA than as a paramedic, but remember, the most independence will always be found at the physician level. I don't say that to start a pi**ing contest with the mid levels, but the fact remains, it will be a long time (if ever) before we find the org chart with midlevel above or lateral to physician. They may work hand in hand, but the hierarchy remains intact.
Best of luck in whatever decision you make. I began by pursuing the PA route, only to find that the pre-reqs were very nearly the same, and in the back of my head I always knew I would constantly be considering if I had truly made the right decision. Ultimately I decided on DO school...so far I have zero regrets.