If anything, the development of the papacy is the unlikely event. If I had to develop a 'probable outcome' for the church of the 400s and 500s, I'd come up with something a lot closer to the Anglican or Orthodox churches than Catholicism.
However, I don't think something like Protestantism (mainstream Protestantism, that is) would be likely to develop. For one thing, once the church was integrated into the Empire it developed increasingly autocratic structures of episcopal and metropolitan oversight which would not allow for such things as elected divines or the easy passage between one church and another. Also, the strong aversion in many Protestant communities to images and a magical understanding of the sacrament would have to wait for a different age - without printing, the majority of people will want to see and feel their God and Saviour. Mary, too, was far too popular throughout the ancient church to be relegated to the dustbin simply because she's not mentioned all that much in the New Testament.
What I'd expect is a church that is subject to the will of secular lords - strong kings pushing around weak bishops - and dominated by the upper classes, with a high regard for learning, but incorporating a powerful ascetic streak. Monasticism is likely to figure (it was riotously popular) and the core of the organisation would be the episcopal see, with its own structures of succession, clerical training, and tithing. Theology would allow a good deal more latitude, though the really big questions would be settled in councils or synods and enforced rigorously. The cult of Saints, Mary, the veneration of icons and relics, and the full range of sacraments, on the other hand, would need a bigger POD - nothing less than a different society - to remove.