Believe me, spending 500EUR banknotes is the smallest issue you're going to face. There are so many ways to exchange it to smaller banknotes including deposit ATMs, bank branches etc.
Impossible. Euro is legal tender in the EU. The only reason they can refuse is because they have no smaller bills handy or some other technical reason. Otherwise, they're breaking the law and you can report them.
Legal tender aside, but each member of the EU has its own rules, so in some places you will even see a sign that clearly shows that you cannot pay with a 500 EUR bill. Today I read an article on a local portal about how a man filled fuel worth 50 EU and tried to pay with a 500 EUR bill, and not only that they did not accept that banknote, but he also experienced considerable inconvenience from the staff - some say that bill is called
"Bin Laden" because of the assumption that it facilitated the financing of terrorism and money laundering.
Of course, after the banknote stopped being printed in 2016, it was not established that the financing of terrorism and money laundering had anything to do with banknotes of that value.