Blocco Note sparito è un Bug, riattivalo:
Premi tasto Win+x scegli App e funzionalità
Clicca su Funzionalità facoltative
Clicca su Aggiungi una funzionalità
Cerca Blocco Note e reinstallalo poi riavvia
Potrebbe essere successa la stessa cosa per Paint
L'app dello Store al momento è solo per la versione Insiders di Windows 10, non è possibile installarla sulle Build stabili.