I am having the same problem
it says I should see the App on the Windows 8.1 app screen
I DO NOT
maybe this helps solve the mystery?
althought I have the CC icon on my desktop and can open it...
From the Start screen, type in Illustrator. You'll see the program show up on the right. Click that.
I found by clicking the app down arrow in the bottom left corner of the app screen gave me a list of new apps
then I clicked on Illustrator
there it began