If that's all he's doing, practice learning how to lay Dins accurately (her side-B) by going to the Temple stage and navigating them through the various paths and stuff. Once you've practiced enough, you should be able to easily lay them a short distance in front of / behind him to ensure that if he side-B's towards you or away, he'll just hit the Dins (and you can follow up while he's in hitstun).
Learning how to land-cancel Nayrus (her neutral-B) could also be useful - if you start Nayrus in the air, and land just as the attack part of the animation finishes, you can cancel it into another attack, jump, shield, grab, or dash sooner than normal. That means that you can use it to safely approach. It's not necessary, but learning how to B-reverse Nayrus can be pretty helpful at times too. Also, since it out-ranges all of his aerials (if he approaches from the side), you can either approach his aerials with Nayrus, or you can retreat while he's close and B-reverse it (which would probably be more effective). Nayrus is vulnerable from the top/bottom though, so if he's above you already, you should just U-smash or U-tilt or something.
Both of those can stuff most approaches fairly easily (including his side-B and F-smash spamming), and allow simple follow-ups. Since F-smash is much shorter, you could also just shield-grab him out of his F-smash (shield before he F-smashes while facing him, and then press A after it hits your shield. L+A or R+A inputs grabs like Z) and chain-grab him from there. On that note...Zelda has a U-throw chain-grab that can also lead into several U-smashes and then end with aerials or F-smash or D-smash.
Remember that so long as you can get Falco off the stage, he's a dead Falco. Learn how to edge-guard Falco, and he should only be able to make it back if you mess up or are too far away.
