I have a German-bought 730, set to US English and United States, and Cortana still doesn't appear. "Sorry," she says when I open her app, "I haven't learned your language yet."
Setting was correct, what the problem was is that it had to download the US English language file (via Phone Update). It was my mistake to think this was already included. It works now.