Humans have indirectly accelerated the rate of evolution (or natural selection if you will), so I doubt it'd take millions of years. Entire ecosystems have changed more in the millennium of modern human activity than many millions of years before that. What makes evolution slow isn't so much evolution itself but the pressures of the environment; drastic, sudden environmental changes spur rapid evolution.
The problem is that day may be millions of years away. It allegedly took nature several million years to evolve bacteria that can digest lignin and cellulose, allowing old fallen wood to decompose in the forest. Coal deposits are from an era when such bacteria were not present.
Even if we had such bacteria, they would only be able to digest plastic under certain conditions. Overall, plastic pollution is here to stay for a very long time.