"state mandated severance pay packages... a direct attack to start ups"
While it's true that many startups fail, I wouldn't go so far as to say severance pay is an attack. You can fire someone with two weeks notice in Spain, paying 33 days of severance for every year paid (used to be 45). AND take home salaries are usually lower.
What is done in practice, to compare worker compensations across countries, is to factor that into the salary equations, it means that workers are a lot more expensive than what the take home salaries might imply, but consider:
Employee A at an US startup has a take home salary of US$ 75.000 will cost US$ 100.000 or so to the employer per year.
Employee B at a Spanish startup has a take home salary of US$ 56.000 (43.000 euros), and it will cost US$ 100.000 or so to the employer per year :) , factoring in severance, healthcare, social security and other benefits.
As jordinl and others stated, most European countries have a three-month trial period for employees as well (edit: and it can be renewed, making the hypothetical 6-months-in non-performer as easy to fire as in the US).
So, an European employee is usually NOT more expensive than an U.S. employee, it requires different considerations (and setting aside money for severance & stuff). It probably is a lot more bureaucratic, but that's it (on the other hand, there are a lot less lawsuits). If the reason for moving into Europe was cheaper salaries, bad luck, but if the reason was an unexplored market, it should work out.
Edit: I do agree that there are some strong laws against beginning your startup in a garage, but the physical location shouldn't be a problem.
About starting a new company: you can buy a pre-made company for 150 euros in Madrid, and probably the rest of Europe, with most of the paperwork solved for you. There are plenty of programs for helping new startups get off the ground (depends on the country, some are more progressive like Finland)