(Sorry, this ended up being really long...)
I think there are a couple of ways to solve (or at least lessen the shock of) this "paradox". First, it can be solved by pointing out the difference between epistemic basing, propositional justification, and doxastic justification. Modest foundationalists don't say that basic beliefs are beliefs that cannot be or aren't justified by other beliefs - they can embrace a quasi-coherentism about the web of propositional justification. They just say that basic beliefs aren't based off of other beliefs. Take the following scenario as an example (taken from here):
Holmes believes that the butler did it. In fact, he knows that the
butler did it: footprints at the scene show that the culprit had size
eleven feet, no-one but the staff were in the house at the time, and
the butler is the only one with size eleven feet. Watson has been with
Holmes every step of the way and so has seen and heard everything that
Holmes has. Watson also believes that the butler did it, but Watson
hasn’t put the clues together like Holmes has. He believes that the
Butler is guilty because he believes in phrenology (contrary to
scientific consensus), and concludes that the butler’s pointed head
and prominent brow are clear signs of his criminal nature.
Both Holmes and Watson possess proposition justification (that is, good evidence) for the butler's guilt. They both believe propositions that taken together make it probable that the butler is guilty. But Holmes bases his belief on the good evidence, whereas Watson doesn't. And so Holmes's belief is doxastically justified (justified in the sense that epistemologists generally care about when discussing the difference between knowledge and true belief, the JTBx sense), whereas Watson's belief is not. Doxastic justification for P consists of having propositional justification for P, and basing one's belief that P off of that which gives propositional justification for P.
A basic belief is a belief that isn't based on other beliefs (it might be based on experience, intuition, or whatever else), but that doesn't mean that other beliefs can't or don't offer additional support for that basic belief. I believe that I'm typing on my computer right now. That belief is not based on other beliefs, it's based unreflectively on my experience (as are most beliefs I form in everyday life), and I'm justified in believing it. But if I stop and reflect on my surroundings, the fact that I am clearly not dreaming, that I haven't just taken LSD, etc. I can gather additional propositional justification for my belief that I'm typing on my computer than is offered merely by the experience of typing on my computer.
Foundationalism might be a basic belief (once again, meaning that it's not based on any other beliefs), but it might have additional propositional justification (still enjoy additional support from the regress argument, etc.). Is foundationalism in fact a basic belief? I do think so. Looking at common epistemic practices, it seems that most people seem to intuitively and unreflectively accept it without ever reasoning out why that is from other beliefs; most people understand that circular reasoning is fallacious, and that proper basing of beliefs can't proceed indefinitely. Foundationalism just seems to be correct to most people who haven't thought about it much, where "seems to be" is a kind of experience or intuition, and not itself a belief.
A second way to solve your paradox might be to accept weaker forms of internalism, where not every justifier needs to be an accessible mental state (only some do). If I believe that P, and P obviously entails Q, do I need to first justifiably believe additionally that P entails Q to be justified in believing Q? This seems to be "mixing levels" (like object language and metalanguage) in a way that leads to Achilles-and-Tortoise-like-paradoxes. Being justified in making correct inferences (and being unjustified in making incorrect inferences) seems to be independent of what I believe about such inferences. From the SEP article on internalism and externalism, quoting Alvin Goldman:
...every traditional form of internalism involves some appeal to logical
relations, probabilistic relations, or their ilk. Foundationalism
requires that nonbasically justified beliefs stand in some suitable
logical or probabilistic relations to basic beliefs; coherentism
requires that one's system of beliefs be logically consistent,
probabilistically coherent, or the like. None of these logical or
probabilistic relations is itself a mental state, either a conscious
or a stored state...
Goldman's passage is a critism of access internalism, but fails against weaker forms that don't require every justifer (like logical and probabilistic relations between propositions) to be an internally accessible mental state. Put this way, structuring one's beliefs as a foundationalist might be necessary for justification, whether or not a subject is aware of the foundationalist requirements (the same way that making an invalid inference is always unjustified, whether the subject is aware of the invalidity). Given this kind of mixed internalism, foundationalism is just a matter of correct inference and correct belief structure, whether the subject realizes it or not (i.e. they don't even need to believe it).
