Lorsque vous installez ou réinstallez Windows 8 (pas sa mise à jour 8.1), vous remarquerez que vous ne serez pas en mesure de télécharger et installer automatiquement les mises à jour de Windows (et d'autres produits Microsoft, le cas échéant) via Windows Upate.
Voici comment résoudre rapidement ce problème.

1. Windows Update produit une erreur 80072EFE sur une installation vierge de Windows 8
2. Mettre à jour le client Windows Update installé sous Windows 8
3. Rechercher des mises à jour sous Windows 8
4. Afficher la liste des mises à jour

1. Windows Update produit une erreur 80072EFE sur une installation vierge de Windows 8

Pour ce tutoriel, nous avons installé Windows 8 Professionnel (mais l'édition n'a pas d'importance) en 64 bits (x64).

Plus précisément, il s'agit de la version 6.2 (numéro 9200).

Comme vous pouvez le voir, Windows Update est désactivé pour l'instant.

Et nous n'avons jamais installé de mise à jour sur cet ordinateur.

Vous tentez de lancer la recherche des mises à jour via Windows Update et le message "Recherche de mises à jour" apparait.

Sauf, qu'une erreur se produira :

Windows n'a pas pu rechercher les nouvelles mises à jour.
Un problème s'est produit lors de la recherche de mises à jour.
Erreurs détectées : Code 80072EFE - Windows Update a rencontré un problème.

2. Mettre à jour le client Windows Update installé sous Windows 8

En fait, si le client Windows Update produit cette erreur "80072EFE", c'est parce qu'il n'arrive pas à se connecter au serveur de mises à jour de Microsoft.
Cela peut se produire si votre ordinateur n'a pas accès à Internet ou si un programme (tel qu'un anti-virus ou un anti-malware) empêche Windows Update de se connecter à Internet.

Néanmoins, si vous venez juste d'installer Windows 8, le vrai problème est simplement que le client Windows Update installé par défaut sous Windows 8 n'est pas à jour et celui-ci n'arrive donc plus à se connecter au serveur de mises à jour de Microsoft.
Heureusement, Microsoft propose une page "Mettre à jour l’agent Windows Update vers la dernière version" où sont référencés les liens de téléchargements pour obtenir facilement la dernière version du client Windows Update pour Windows 7 SP 1 et 8 (ainsi que les éditions serveur correspondantes).
Une fois le client Windows Update mis à jour, votre ordinateur sera en mesure de rechercher et télécharger automatiquement toutes les mises à jour nécessaires via Windows Update.

Sur cette page "Mettre à jour l’agent Windows Update vers la dernière version", vous trouverez une section "Packages autonomes pour Windows 8 et Windows Server 2012" avec 2 liens de téléchargements pour Windows 8.
Choisissez le lien de téléchargement adapté à votre architecture de Windows :

• 32 bits (x86) : Toutes les versions x86 de Windows 8 pris en charge (KB2937636)
• 64 bits (x64) : Toutes les versions x64 de Windows 8 pris en charge (KB2937636)

Info : si ces liens de téléchargements ne fonctionnent plus, cherchez cette mise à jour KB2937636 sur le catalogue Microsoft Update.

Comme expliqué au début de ce tutoriel, nous avons installé une version 64 bits (x64) de Windows 8.
Nous téléchargeons donc la version x64 de cette mise à jour : KB2937636.

Par défaut, la page est affichée en anglais (English), mais vous pouvez sélectionner "Français" dans la liste pour traduire la page automatiquement.
Ensuite, cliquez sur le bouton "Télécharger".

Le fichier qui sera téléchargé est :

• Windows8-RT-KB2937636-x64.msu (si vous avez choisi la version 64 bits)
• Windows8-RT-KB2937636-x86.msu (si vous avez choisi la version 32 bits)

Pour installer cette mise à jour, faites un double clic sur le fichier "Windows8-RT-KB2937636-x...msu" téléchargé.
Une fenêtre "Programme d'installation de Windows Update en mode autonome" apparaitra.

Patientez pendant l'installation de la mise à jour.

Une fois la mise à jour installée, vous devrez redémarrer votre ordinateur.

Pendant le redémarrage, le message "Configuration des mises à jour de Windows - xx% effectués" apparaitra.

Ensuite, retournez dans Windows Update.