Can a card effect make a creature block one that it otherwise could not?
Yes, the creatures will still be blocked by tokens. See the ruling on Nature Shields its Own:


  The Plant token blocks the attacking creature even if the block couldn't legally be declared (for example, if the attacking creature has flying).


This is because things like flying and protection only affect the declare blockers step. The prevent a creature from being declared as a blocker. But Nature Shields its Own kicks in at the end of the declare blockers step; it is not affected by evasion abilities.