From my experience, Authorize.Net would be your best bet. Most banks have at the very least a 3rd party relationship with Authorize.Net. This is the simplest choice that I have found to get your cart up and running.
I personally prefer using Authorize.Net over PayPal. The merchant fees are better with Authorize.Net. PayPal Pro is more expensive monthly and per/transaction.
Contact your bank and I think you'll find someone that can get the process started.