From a British prespective, it is completely acceptable.

To me what you say sounds natural. I'd probably say it in the plural though: Where are the nearest toilets? Sure 'nearest' isn't needed, but I'm sure I've used it like that.

Yeah, don't use 'restroom' in the UK. It sounds odd. I think of a room with beds and sofas :P Also I find it odd asking for a 'bathroom' in public place, since they don't have baths in them.

I would say "Excuse me where is the toilet?" I am from the UK so I don't usually say bathroom or restroom.But if I were in  the USA I might use one of those so as to be more polite and clear.

Thank you all for your comments and for the pieces of advice. I learned a lot from you.

Nope, it's fine. 

You could say: "is there a toilet around here?" or "are there any toilets around here?"