I once had the exact opposite situation to your query. I believed in the existence of gods (not God the Creator). When I came upon Buddhism rejection of gods, I tried to make sense of it. One thing about Buddhism I realized is that what it taught can be observed; maybe not in the actual form but in a representative form.
If you look at gods and devas as higher realm beings, you probably will be wondering is there really such beings. How about if I show you a lower realm - that of the animals and insects. Our realm as human is higher than animal and insects. Animals and insects might see us as in term of gods and devas. They, animals and insects, lived shorter life span compared to us humans just as we humans live shorter life span compared to the gods and devas. We can interact with the animal and insects for good or evil (e.g. we can extinguish a fire that threatened a bee-hive or we can destroy a bee-hive) just as the gods can interact in human affairs for good or evil. Now, to a human, extinguishing a fire only requires us to turn on a tap and hose it down, but to a bee, it would seem that the human can command water; it would be magical. As for Buddha's magical power in the angulimala sutta, the Buddha could be doing something that the has realized in his enlightenment but is miraculous to us.
Before I took up the meditation to establish mindfulness, there was an advice to try it before making any judgement and see it for myself. I did just that and the effect was real and present even for a mediocre practitioner like myself. It would not be beyond believe for the Buddha to have achieved some thing we perceived to be magical power.