A few years back I re-wrote a old Greek legend using Nintendo charactors such as Mario, Peach and others. My question is if I can publish this as a children’s book or what I need to do in order to get permission.
You would need to ask Nintendo’s permission to use them as characters.
and count on them to say no.
The issue here is trademark law. Nintendo has trademarks on all of their iconic characters, and so nobody can use those characters without their permission. They retain this right for as long as they continue to defend their trademarks: They could in principle decide tomorrow that they don’t care and stop going after infringers, in which case the characters would pass into the public domain, or they could (assuming the law stays the same) continue to defend and retain their rights for the next thousand years.
They’re free to set whatever conditions they like on who’s allowed or not allowed to use their characters, but the most significant condition is almost always going to be money: They want anyone who’s using their characters to pay them a lot, probably more than you can afford.
You’d probably have better luck selling them the story and letting them worry about publishing.