Looking at this map of state licensing regimes (darker is more onerous, with AZ being the worst), it is hard to correlate with states being Republican or Democrat. That doesn't surprise me, because I have always thought the urge to restrict competition and protect incumbents has always been a bipartisan enterprise.
So I sat and thought for a minute about my home state of AZ. Why is it the worst? We have a pretty good libertarian history here, from Goldwater onwards. We have at least one fairly libertarian Senator (Jeff Flake). So what is the deal?
My hypothesis is that it is related to immigration. The same majority Republican legislators who are generally open to free markets simultaneously have an incredible fear and loathing of immigration. Perhaps our onerous business licensing regime is driven by nativists wanting to protect themselves from competition by new immigrants, immigrants who would struggle to compete onerous licensing requirements?
So what does this map look like vs. immigrant population density? Via Wikipedia, here are the states on density of Hispanics
Hmm, we might be getting somewhere, but its not a perfect fit. So instead, let's hypothesize that business licensing is aimed at non-white, non-hispanic groups in general (similar to early justifications for the minimum wage as a way to keep black workers migrating from the south out of traditionally "white" jobs). I cannot get it by state, but the map below by county looks pretty dang similar to the licensing map. Areas in blue have above average percent of non-whites, red is below average.
Not a perfect fit certainly (one would expect Texas to be more onerous), but perhaps close enough to treat the hypothesis seriously. I had always thought that I would be the last one to play the race card in a policy analysis, but business licensing tends to have an inherently base motive (protect one group from competition from another group) that is pretty easy to square with racial and ethnic fear.