Okej, poradziłem sobie.
Dziękuję wszystkim za podpowiedzi. Z racji, że w WindowsPhone nie znajdziecie opcji typu "eksportuj", dla potomnych napiszę jak to zrobiłem krok po kroku.
Kontakty były połączone z kontem Microsoft. W moim przypadku była to poczta hotmail, choć domena nie ma żadnego znaczenia. Zalogowałem się na swoje konto z poziomu komputera i przeglądarki. Możecie wejść na outlook.com, hotmail.com, itd., strona i tak was przekieruje pod właściwy adres. Wchodzimy w kontakty, zaznaczamy wszystkie, z opcji "zarządzaj" wybieramy "eksportuj na potrzeby Outlook.com i innych usług". Pobrany zostanie pliczek Outlook.csv. Następnie przechodzimy do Gmail'a, logujemy się na pocztę. Następnie klikamy na napis "Gmail" w lewym górnym rogu i wybieramy kontakty. W moim przypadku kontkaty tam zapisane były nieaktualne więc je usunąłem i dalej wybrałem import z pliku, wskazałem plik Outlook.csv. Kontakty się wczytały, więc następnie wybrałem opcję eksportu, tam chyba były 3 więc wybrałem tą, która w nazwie miała Apple, utworzył sie plik contacts.vcf i to jego wskazałem przy imporcie na portalu iCloud. Droga trochę zagmatwana, natomiast Gmail był potrzebny, gdyż iCloud nie zaimportuje kontaktów z pliku *.csv.