I agree with the other posters. Do the Post-Bacc. You already have clinical know how. The reason your getting rejected is because of your GPA!
I'm starting up a paramedic program in September, and I've been running BLS for the last year. A 1 year medic program (like mine) is going to teach you the material, put you through tons of clinicals, and try to get you to pass the NREMT-P exam.
Even if you get certified in a year's time, it doesn't mean your going to be capable (you lack a lot of experience). The ADCOM is going to see right through it. Even if you think your doing it because you want to gain more medical experience and "help people" (medicine yada yada), they're still going to see it that you did it to try to influence your acceptance.
You should only become a paramedic if you want to do it for a career. Its alright if a paramedic who's been working in the field for several years decides "hey, I want more", and then decides to apply to med school.
While your at it, why don't you get your RN, PA, DDS, license etc...
Just kidding with you, but I'm sure you get the point.
My advice ---> keep working at your CNA job and get into the post-bacc program. The things at the top of the tier for getting into med school are MCATS and GPA. You got a great MCAT score (30); just work on your GPA.
=)