There are a lot of hosted ecommerce solutions, like Shopify and Yahoo Merchant Solutions, etc. If you're new to e-commerce, you should probably use one of those. Those sites should set up all of the payment processing for you.
But a store with that level of regular revenue definitely shouldn't be using PayPayl Payment Standard. That is for low-revenue small businesses. It takes the customer off-site, takes a higher percentage, and is generally less professional.
Personally, I would have them talk to their bank about opening a merchant account and find an online payment processing gateway (one with a payment module for Magento) for Europe. Often, those two services are packaged together, and the sales reps for the bank, payment processor, or merchant account provider will walk them through account creation. You don't need to, and shouldn't be, involved. All you need is access to the payment processing API.
Then just install Magento and configure the payment processing options to use the payment gateway the client signed up with.
If you want to use Drupal UberCart, then you just need to see what payment processing modules are available for it and pick a payment processing gateway that is supported. Otherwise, if you pick one that isn't supported, you'll have to write your own module based on documentation from the gateway provider. This usually isn't too hard, and I had to do this on my very first e-Commerce site, but if you want to save time, you ought to just use a popular payment processor with a well-supported API.
Though, since this store has a high sales volume, I would consider trying out Magento Pro or Enterprise. Those are the only versions that are PA-DSS compliant and come with support. But really any version of Magento will provide a more robust online store than DrupalUbercart, which itself is probably more suited to smaller sites.