There is no AutoCompleteBox control that can be used when building Windows Store apps in C# and XAML so I decided to create one, because I needed it for a project. Currently it supports only String collections and the selected value must be accessed using code behind, but this will hopefully change.
The project is hosted on my Bitbucket so you can check it out at https://github.com/igorkulman/AutoCompleteBox, forks and code contributions are welcomed. Nuget package is available at https://nuget.org/packages/AutoCompleteBoxWinRT.
Installation using Nuget: