For Christians who completely reject the story of Adam and Eve in any literal sense, the scriptures don't provide any definitive alternative. Thus you are entering into the realm of conjecture. Indeed, even if we were to take all of Genesis at face value, there isn't a lot of detail.
That said, I think I would approach this problem by questioning the axioms of the argument. Namely: is it true that if God is benevolent and omnipotent that there thus cannot be any suffering/death in a perfect world?
I would argue that a certain amount of suffering is actually beneficial to our growth as individuals and, at a more basic level, to our survival. A little cut from a knife teaches you that a knife is dangerous and to be handled with care, for instance.
Additionally, death is necessary for new life. You constantly hear about how we are running out of resources due to our growing populations - imagine if nothing ever died! Thus death enables the possibility for new life. Even if we didn't need to eat, the planet would quickly get overcrowded with life and we'd be miserable.
If we are focused on Theistic Evolutionists, they will further argue that God used evolution as the means through which he created life in all its various manifestations - which requires reproduction and ultimately death (as noted above).
Let us also note that physical death is not the end from a Christian perspective; merely a necessary step in transitioning from our natural bodies to spiritual bodies.
Finally, both God and Christ are believed to have suffered and, in the latter case, even died despite being sinless. So Christianity would appear to reject the notion that perfection = no suffering/pain/death.