My understanding of the terms is that recato means something that has much more to do with decencia than to 'modestia`. I use them more or les this way:
Modestia is indeed modesty. I use to show the humility of somebody about skills or good deeds. It is not shyness and I consider it a good thing (not being eager to brag or show off), but of course other might think that humility might have to do more with somebody not daring to speak for himself or herself and saying that people who are modest are so because they are just shy or pudorosos.
'Decencia' is also almost self-explanatory. Do what is considerer decent or appropriate (which might be up to the society to decide).
Recato would be to apply "decency" to your dress code or behavior. If I hear
Vestía recatadamente
I imagine a woman who is trying not to show much of her body (almost as if she was dressing like my grandmother would had 70 years ago: skirt under the knees, not showing the neckline...). Maybe that could be where pudor comes across too. I guess that you can apply "recato" to behavior too (comportarse con recato) but the inflections is that is more about following social convention that about modesty, shyness or even pudor. And that acceptance of the social rules is "decency".
If somebody
Se comporta con recato
might imply that he is not speaking out of time, doing anything inappropriate, etc.
Note: I'm from Spain.