Do we need to believe in Buddhist stories to be a real Buddhist? Some suttas and the dhammapada contain stories with things not very easy to verify, such as people flying, living 8.000 years, teletransportation, etc. 

Some of those are related to the psychic powers of the Buddha and that is easier to believe as he was an enlightened being; however some are not related to that.

Buddha always encouraged us to verify and contemplate things. Will having doubt about Buddhist stories and legends interfere with Buddhist practice?
You should not believe all the stories to become a Buddhist dear friend. Instead you should believe Noble Eightfold Path and taking refuge in the triple Gems (Load Buddha, Dhamma and Sangha). Taking refuge doesn't mean that the person has to pray for them or looking forward until they do something for you. We have to believe Lord Buddha, Dhamma and Sangha then we have to follow the path which is showed by them. They are guides and helpers so followers have to follow the path. 

If someone loose their courage to follow the path due to the stories that is the best enmity one can do for him/her self. First clarify everything about Noble Eightfold Path and follow it. Then when you gaining wisdom due to the follower, you will be able to identify whether the stories are true or false.  

when talking about teleportation, we are in a era of quantum teleportation. even now with the existing technology we can perform teleportation on quantum particles like photons. but the problem is on the communication channels. if we divide our body into quantum particles and begin to teleport them, it will take millions of years to complete. If scientists develop a mechanism to build high speed communication channel with using quantum entanglement, we will have a teleportation era in near future. So don't categorize stories just as fairy tails or believe at once. Remember stories and follow the path then you will find facts do decide.