In some places red tape is a big issue, but I don't think it's the whole story. Starting a small business in Denmark nowadays is extremely streamlined: you can do the entire registration process for the Danish equivalent of an LLC online, and your business is registered within a day or so. It's so easy that it's become common for people to start a company even for small-scale side-business stuff. It's also fairly easy to hire and fire people (one prong of the "flexicurity" policy [1]).
I think a big problem has been the economics of scale you mention, because Europe has not really functioned as a common market. One part is language. This is changing a bit (at least here), and most Danish tech startups now make their products English-first, or even English-only, which greatly increases the odds of international adoption. Some is more cultural, though; we don't read French or Italian or German media, and nobody else reads Danish media, so things that get a "buzz" in one country travel fairly slowly cross-border, while American media spreads quickly. Probably a lot more factors of this sort.
One issue of incentives, though, is that it can still be in many cases an individually rational choice to target a more "provincial" market. If you're a Danish startup and identify a Danish-specific underserved market, you have less potential for growth, but may have higher probability of at least modest success, due to much less competition. So even if it's better for Europe as a whole for startups to target a broad, international market, it might be rational for individual startup founders to target smaller, country-specific markets. American startup founders to a large extent lack this choice, because there are not many tech market niches which are, say, Tennessee-specific.
[1] https://en.wikipedia.org/wiki/Flexicurity