I watched this anime several years ago. Although I am calling it an anime, this is not to imply that it does or does not originate from Japan (I don't know where this is from). This anime involves a group of travellers in a world populated by creatures such as goblins. Magic is definitely used throughout the course of the story. Here are some scenes which I remember.
In one scene, one character is talking to a group of listeners about... something. He mentions a god named Paladin (I think that's what his name was. I could be wrong). Just then, a bystander shows up and exclaims "This is blasphemy, heretic! You're ruining our youth, call the guards!". Now, the anime was dubbed in Russian, so the wording in the original is not exact.
In another scene, the place where the characters are is attacked by goblins. A notable feature about them is that they have a round hole where in their faces where a human's nose would be. One of them gets into a swordfight with a character. The character asks "What are you worms doing in here?", to which the goblin replies with "Worms? At least I'm not a hybrid", followed by spitting into the character's face out of said nose-hole, temporarily blinding him.
The third scene which I remember involves the party arriving in some place where prisoners are housed. I don't know if they are PoWs or not. They talk about Paladin and how, no, the gods have not abandoned humanity, but humans abandoned the gods through their lack of faith. One of the prisoners remarks to a female main character that there is a man in the cell with them who is dying of some disease (I think it may have been measles) and that, if what she says is true, then the woman main character can cure the man. She lays her hands on the man and the man is cured of his disease.
In the last scene which I remember, the big bad is doing something, when suddenly, Paladin appears before them. The big bad exclaims "Paladin? But the prophecy hasn't come true, how could you return?", to which Paladin replies something along the lines of "Faith".
