Hiring people in multiple European countries and payroll taxes

I've been working on the basis of a consultancy contract recently, and as it happens also on selling a SAAS based project. In my experience you don't quite need to set up legal establishments in each country, as Dmitri mentioned. You do need to watch out for local finesses, e.g. the maximum duration of a consultancy contract. At start you probably are OK but watch out if you're using someone for longer than 2 years in a row; in some countries a 2+year contractual relationship may be considered as a half full time employment. Side remark: if you're from North America and if this is your first effort into Europe, please make sure that your financial processes can cope with VAT.

No, of course not, you hire people under a consulting services agreement. You wire them the money and paying taxes is entirely their responsibility. You don't need to set up legal entities there, nor do you need to pay their taxes, medical insurance, or anything else.