Are you going for a "stains on the parchment" effect, or a "drawn on the parchment" effect? In the latter case, you should certainly have at least one dark colour for important gameplay elements (characters, interactive objects) that isn't found on in the parchment texture itself.
In the former case, you should study GameBoy games like Wario Land and Trip World, which use monochrome 4-colour palettes to great effect.
Personally, I think allowing yourself one darker colour (doesn't have to be an additional colour, you could darken your darkest one) would be best. Your current palette looks washed out and dull to look at. Even if that's intentional, most players prefer something with more contrast.
The trick in either case is to avoid using your darkest colours anywhere the characters might overlap, have them always on top of your lightest colours. This is as much a palette challenge as it is a tile- and level-design one.