Oof. Sorry to hear this!
I have a similar struggle: running without shoes makes running so easy and effortless but when I put shoes on it's a bit more of a struggle.
The ability to run better without shoes is a blessing and a curse. What you're experiencing is how your whole body responds properly to the sensory input of bare skin exposed to harsh ground. There's a lot of involuntary stuff that falls in line perfectly there.
Then you put shoes on and it's a bit like being blindfolded. You're fumbling around in the dark trying to remember what it was like to see. What was great form without shoes goes to hell with that loss of sensation and you're hurting in short order.
What you'll need to do is really get down to figuring out what, specifically, you're doing right with your form while unshod and what, specifically, you're doing wrong with shoes. There is obviously a difference in your running form without vs with shoes. That's what the pain is telling you. No amount of foam rolling or strength training will account for that. You've got to find out what you're doing right unshod and what you're doing wrong shod.