Unfortunately, I do not know where he was from. I've ordered a copy of his naturalization papers to see if they will tell me (they may not, since I think they were filed prior to the 1906 changes), and if I find out, I'll respond. I did some looking around about the Hoxeyville/Henderson area, and found that it was originally founded as a lumber center. I don't know how far it is from Cadillac, but I do know that more than a few family members ended up in Cadillac over the years.
I will ask my dad if he knows if his grandparents were Lutheran or Baptist - that was an interesting issue you pointed out.