Je crois bien avoir été victime d'un pirate ... help svp

Bonjour,

Il y a environ 2 heures j'ai reçu un appel d'une personne parlant anglais.
Je n'ai pas un bon niveau d'anglais mais je comprends que ce dernier travaille pour Microsoft et il m'indique vouloir résoudre le problème lié à mon PC.

Effectivement 1 de mes PC a un soucis depuis 2 mois puisque du jour au lendemain, lors du démarrage, l'écran est noir (plus d'arrière plan !), et un message en bas à droite de l'écran indique un truc du genre : "Votre logiciel Microsoft est peut être une copie ..." ou quelque chose dans ce genre.
Je précise que je ne suis pas du tout copain avec l'informatique et qu'il s'agit d'un vieux PC utilisé par ma fille pour de temps en temps accéder à des jeux on-line.

D'abord réticent à sa démarche (je suis surpris que ce ne soit pas Microsoft France qui m'appelle) je décide de le renvoyer !
Et c'est là que le gars (très fort !) m'indique que si je ne règle pas mon problème, tous mes comptes Microsoft seront bloqués !
De peur, et étant une buse en informatique, je décide donc de l'écouter.
Pas à pas et avec une patience hors norme dû à mon niveau d'anglais, il me dit de cliquer ci et là pour me montrer tous mes problèmes, ... avec effectivement à la clef une liste entière de "warning" + la preuve que ma licence Microsoft n'est plus bonne.
Et cerise sur le gâteau il me donne même un numéro (genre une douzaine de chiffres et lettres) en me demandant de le vérifier l'exactitude sur mon écran afin de me donner la preuve qu'il bosse bien chez Microsoft !

Je fini comme un con (y a pas d'autre mots) par lui laisser la main sur le PC pour qu'il puisse corriger.
C'est seulement quand il fini par me parler d'argent pour renouveler ma licence, ... que je décide de me connecter sur le net sur un autre PC à porter de main, ... et là en 2, 3 cliques je comprends que j'ai peut être à faire à un pirate.
Je lui indique donc que je souhaite mettre fin à la conversation et essaye de lui retirer la main sur le PC, ... j'ai eu énormément de mal à prendre la main et j'ai dû passer par un "alt ctrl delete" pour shunter team wiewer, ... pendant ce temps là, il a eut le temps de bidouiller.

Après avoir mis fin à l'appel, je décide de regarder un peu mieux les info sur le net et télécharge une application pour scanner et nettoyer le PC (Malekal je crois).
Mais le nettoyage nécessite le redémarrage du PC, .... et là je me rends compte que l'enfoiré a eut le temps de mettre un mot de passe pour démarrer le PC.
Je me suis fait avoir comme un idiot, ... profitant de la barrière de la langue et de mon incompétence, .... je m'en veux, mais c'est fait.

Suite à une info vue sur le net, ... j'ai d'en un premier temps :
Retiré la connexion internet à cet ordinateur.
J'ai changé le mdp de ma boîte mail principale.
J'ai changé le mdp de ma connexion internet sur mes comptes

Dois-je faire autre chose pour limiter la casse ?
Mon ordinateur est-il récupérable ?

Merci d'avance à ceux qui voudront bien prendre la peine de lire et m'aider.
Désolé pour la longueur mais j'ai souhaité être le plus détaillé possible.