In general private banks should have no problem with it but might not necessarily offer cash services to non-customers. If nothing else works, you should however be able to exchange them at one of the branches of the Banco de España.
No matter what you do, if you want to change a large amount of cash, you might have to present ID or satisfy some other reporting requirement.