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](http://www.new-euro-banknotes.eu/News-Events/PRESS-RELEASES-PRESS-KITS/ECB-ENDS-PRODUCTION-AND-ISSUANCE-OF-%E2%82%AC500-BANKNOTE).

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.