Well their perception matters because you are just coming out of a "probationary" period.
Don't quit this job, before you begin the other one, since the new one doesn't actually have a start date.
Did you approach the person who set the 30 day conversion date ?
I work at a place where we get paid bi-weekly - hence a person would be waiting 2 weeks or longer after the conversion date to see this stuff reflected on their pay stub - . You are barely 5 days out of the probaationary date. I think maybe you are expecting quicker action on their part than is realistic. Disclaimer, I do not work in HR, but i imagine it takes longer that a day to get someone signed onto their healthcare benefits system.
Stick it out + keep showing up if the staff are nice, it seems like a decent job with relatively quick promotion potential. I bet they go thru a lot of short term employees being a construction firm [ i think ? ]. It isn't their fault you weren't on Medicaid before you started . Ask about the situation once a day, talk to different people if necessary. Holding out for another month to get health insurance shouldn't be a big deal.