I’m no expert, but from what I have seen, the Spanish seem to have a different attitude to childcare than the UK and the USA, and it is less likely that both parents will work and leave their children with anyone other than a family member - especially in rural areas.
In London, for example, there are hundreds of agencies and day-nurseries, and it is much more the norm for both parents to work full-time and not have a non-working family member to leave their children with.
The problems you have experienced with nationality are nothing personal I’m sure - it is probably down to the way the agencies offer choices to their prospective clients, by asking if they have a preference. Even Hungarian families in Spain would benefit from a Spanish-speaking nanny or au-pair if they are not fluent themselves, but I think that it is just unfortunate that you are in a profession where demand doesn’t exceed the supply in your chosen location.
You probably wouldn’t do any better as a carpet-fitter in Malaga or a central-heating engineer in Tenneriffe either 😊
It might be worth trying to contact a day-nursery in Barcelona directly, rather than to get an agency to place you with a family, but there are probably more day-nurseries in Alicante and Murcia than Barcelona.
Another thought - many hotels offer their guests a day-care service for their children, would that be worth a try?
