I beleave you have to use differetn controls for each platform.
Check this: How to use Auto Complete Box in Windows Phone - Wiki
In any case you can write your own using standart textBox and ListBox filtered by TextBox. It will take some time but it's not so hard and gives a lot of understanding how controls works.
Auto complete box is replaced by auto suggest box in the new Windows Phone 8.1 SDK. You can check that one out it is very simple to use, I do not know if it works with Windows 8 & 8.1.