Sachverhalt:
A.
A.a. Gestützt auf den von Rechtsanwalt A._ gegen die B._ Srl (mit Sitz in U._, Italien, und vertreten durch C._) erwirkten Arrestbefehl Nr. xxx vom 5. November 2014 verarrestierte das Betreibungsamt der Bezirke Leuk und Westlich-Raron am 6. November 2014 gestützt auf <ref-law> das auf den Namen von C._ lautende Bankkonto Bank D._ (IBAN CHyyy) für Honorarforderungen im Umfang von Fr. 34'702.35 nebst Zins zu 5 % seit 24. April 2014. Der Arrestbefehl und die Arresturkunde vom 12. November 2014 wurden zwecks rechtshilfeweiser Zustellung an die B._ Srl am 12. November 2014 mittels eines Antrags auf Zustellung eines Schriftstückes im Ausland an das Tribunale di Verbania versandt. Der Antrag ging zusammen mit den Schriftstücken am 19. November 2014 beim Tribunale di Verbania ein.
A.b. Am 19. November 2014 stellte A._ das Arrestprosequierungsbegehren. Das Betreibungsamt stellte den Zahlungsbefehl (Nr. zzz) am 20. November 2014 aus und versandte ihn am 21. November 2014 rechtshilfeweise mittels Antrags auf Zustellung an das Tribunale di Verbania. Beim Tribunale di Verbania ging das Begehren am 9. Dezember 2014 ein.
A.c. Am 12. Dezember 2014 sandte das Tribunale di Verbania ein Aktenstück mittels eingeschriebener Postsendung an C._ in U._. Diese Sendung wurde am 18. Dezember 2014 ausgehändigt.
A.d. Nachdem weder die Zustellbescheinigung für den Arrestbefehl noch für den Zahlungsbefehl beim Betreibungsamt eingegangen waren, erkundigte es sich am 26. Januar 2015 per E-Mail nach deren Verbleib. Am 28. Januar 2015 stellte das Betreibungsamt dem Tribunale di Verbania eine Kopie des Gesuchs um Zustellung vom 21. November 2014 (betreffend den Zahlungsbefehl) und eine Kopie des Zahlungsbefehls zu. Die Kopie ging am 29. Januar 2015 beim Tribunale di Verbania ein.
A.e. Am 4. Februar 2015 bestätigte der Zustellbeamte auf einem Zustellungszeugnis, dass am 18. Dezember 2014 auf postalischem Weg in der gesetzlich vorgeschriebenen Form ein Aktenstück an C._ in U._ zugestellt worden sei, welches am 12. Dezember 2014 der Post übergeben worden war. Als zurückgesandtes Schriftstück wurde "Atto giudiziale: precetto esecutivo" angegeben.
A.f. Am 19. Februar 2015 wurde der B._ Srl der Zahlungsbefehl (Nr. zzz) zugestellt. Der Zustellungsbeamte bestätigte am 4. April 2015, dass C._ am 19. Februar 2015 ein Aktenstück zugestellt worden sei, das am 16. Februar 2015 der Post übergeben worden war. Als zurückgesandtes Schriftstück wurde "Atto giudiziario" angegeben.
A.g. Am 23. Februar 2015 erhob die B._ Srl Rechtsvorschlag.
B.
Am 2. April 2015 reichte A._ Beschwerde gegen die Zustellung des Zahlungsbefehls vom 19. Februar 2015 ein. Er verlangte im Wesentlichen, die Zustellung vom 19. Februar 2015 aufzuheben und festzustellen, dass der Zahlungsbefehl bereits am 18. Dezember 2014 zugestellt und dagegen kein Rechtsvorschlag erhoben worden sei.
Mit Entscheid vom 8. Mai 2015 wies das Bezirksgericht von Leuk und Westlich- Raron als untere Aufsichtsbehörde die Beschwerde ab.
C.
Dagegen reichte A._ am 21. Mai 2015 Beschwerde beim Kantonsgericht Wallis als oberer Aufsichtsbehörde ein. In Abänderung des angefochtenen Entscheids beantragte er festzustellen, dass die Zustellung vom 19. Februar 2015 nichtig sei, dass der Zahlungsbefehl am 18. Dezember 2014 gültig zugestellt und kein Rechtsvorschlag erhoben worden sei und die Fortsetzung der Betreibung ab dem 29. Dezember 2014 verlangt werden könne. Allenfalls sei die Sache an das Bezirksgericht zurückzuweisen.
Mit Entscheid vom 17. März 2016 wies das Kantonsgericht die Beschwerde ab.
D.
Am 4. April 2016 (Postaufgabe) hat A._ (Beschwerdeführer) Beschwerde in Zivilsachen an das Bundesgericht erhoben. In Abänderung des kantonsgerichtlichen Entscheids beantragt er festzustellen, dass die Zustellung vom 19. Februar 2015 nichtig sei, dass der Zahlungsbefehl am 18. Dezember 2014 gültig zugestellt und kein Rechtsvorschlag erhoben worden sei und die Fortsetzung der Betreibung ab dem 29. Dezember 2014 verlangt werden könne. Allenfalls sei die Sache an das Kantonsgericht zurückzuweisen. Die Kosten des kantonalen und des bundesgerichtlichen Verfahrens seien der B._ Srl (Beschwerdegegnerin) aufzuerlegen und diese sei zu verpflichten, ihm im bundesgerichtlichen Verfahren eine Parteientschädigung zu entrichten.
Das Bundesgericht hat die Akten beigezogen, aber keine Vernehmlassungen eingeholt.

Erwägungen:
1.
Die Beschwerde in Zivilsachen, die sich gegen einen Entscheid der oberen Aufsichtsbehörde in Schuldbetreibungs- und Konkurssachen wendet, erweist sich grundsätzlich als zulässig (Art. 72 Abs. 2 lit. a, Art. 74 Abs. 2 lit. c, Art. 75, Art. 76, Art. 90, Art. 100 Abs. 2 lit. a i.V.m. <ref-law>). Auf einzelne Eintretensfragen ist im Sachzusammenhang einzugehen.
2.
Gegenstand des Beschwerdeverfahrens ist die Frage, ob der Zahlungsbefehl Nr. zzz vom 20. November 2014 erstmals bereits am 18. Dezember 2014 an die B._ Srl (vertreten durch C._) in U._ zugestellt worden ist, oder ob die erste Zustellung erst am 19. Februar 2015 erfolgte. Während der Beschwerdeführer die Ansicht vertritt, der Zahlungsbefehl sei bereits am 18. Dezember 2014 zugestellt worden, ist die Beschwerdegegnerin der Auffassung, ihr sei an diesem Tag einzig die Arresturkunde zugestellt worden.
2.1. Das Kantonsgericht hat erwogen, sowohl am 18. Dezember 2014 wie auch am 19. Februar 2015 sei jeweils eine Sendung des Tribunale di Verbania an die Beschwerdegegnerin in U._ zugestellt worden. Unbestritten sei, dass am 19. Februar 2015 ein Zahlungsbefehl in der Betreibung Nr. zzz zugestellt worden sei. Ob es sich dabei um den am 21. November 2014 an das Tribunale di Verbania versandten Originalzahlungsbefehl oder den am 28. Januar 2015 nochmals diesem Gericht zugestellten Zahlungsbefehl handle, sei nicht eruierbar.
Dass am 18. Dezember 2014 zwei Schriftstücke zugestellt worden seien, sei nicht nachgewiesen. Es stehe fest, dass seit diesem Tag die Beschwerdegegnerin im Besitz des Arrestbefehls sei. Aus den Zustellungszeugnissen vom 4. Februar 2015 und vom 4. April 2015 gehe nicht hervor, was für eine Urkunde an die Beschwerdegegnerin zugestellt worden sei. Zwar sei auf dem Zustellungszeugnis vom 4. Februar 2015 als zurückgesandtes Schriftstück "Atto giudiziale: precetto esecutivo" aufgeführt. Dieser im Zustellungszeugnis als zurückgesandtes Schriftstück erwähnte Zahlungsbefehl sei am 16. Februar 2015jedoch beim Betreibungsamt nicht eingegangen. Mithin sei die Zustellung des Zahlungsbefehls am 18. Dezember 2014 an die Beschwerdegegnerin nicht erwiesen. Somit sei auch nicht nachgewiesen, dass der Zahlungsbefehl zweimal zugestellt worden sei. Wäre dem so, so wären drei Zustellungszeugnisse an das Betreibungsamt zurückgesandt worden (eines für den Arrestbefehl und zwei für den Zahlungsbefehl). Es stehe aber fest, dass nur zwei Zustellungszeugnisse zurückgeschickt worden seien.
2.2.
2.2.1. Der Beschwerdeführer macht in erster Linie eine willkürliche Feststellung der Tatsachen geltend (<ref-law>). Daneben rügt er die Verletzung von <ref-law>, Art. 66 Abs. 3 und Art. 72 Abs. 2 SchKG sowie von Art. 5 des Haager Übereinkommens vom 15. November 1965 über die Zustellung gerichtlicher und aussergerichtlicher Schriftstücke im Ausland in Zivil- oder Handelssachen (SR 0.274.131). Diesen weiteren Rügen kommt jedoch keine selbständige Bedeutung zu, da es vorliegend nur um die die Tatsachenebene betreffende Frage geht, ob der Beschwerdegegnerin der Zahlungsbefehl bereits am 18. Dezember 2014 oder erst am 19. Februar 2015 zugestellt worden ist. Insbesondere hilft die Rüge der Verletzung von <ref-law> (vgl. <ref-ruling> E. 2 S. 118) nicht weiter: Zwar erbringen öffentliche Register und öffentliche Urkunden für die durch sie bezeugten Tatsachen vollen Beweis, doch gilt dies nur, solange nicht die Unrichtigkeit ihres Inhaltes nachgewiesen ist (<ref-law>). Dieser Nachweis ist an keine besondere Form gebunden (<ref-law>). Dieser Gegenbeweis ist vom Obergericht als erbracht angesehen worden (da nach der ersten Zustellung kein Zahlungsbefehl zurückgesandt worden sei und nicht drei Zustellungszeugnisse ausgestellt worden seien), was eine Frage der Beweiswürdigung bzw. Tatsachenfeststellung betrifft, die vom Bundesgericht nur unter den Voraussetzungen von <ref-law> (dazu sogleich E. 2.2.2) überprüft werden kann.
2.2.2. Der vorinstanzlich festgestellte Sachverhalt ist für das Bundesgericht grundsätzlich verbindlich (<ref-law>). Die Feststellung des Sachverhalts kann nur gerügt werden, wenn die Feststellung offensichtlich unrichtig - d.h. willkürlich (<ref-ruling> E. 1.5 S. 130 mit Hinweis) - ist oder auf einer Rechtsverletzung im Sinne von <ref-law> beruht und die Behebung des Mangels für den Verfahrensausgang entscheidend sein kann (<ref-law>). Will der Beschwerdeführer die Sachverhaltsfeststellungen der Vorinstanz anfechten, muss er darlegen, inwiefern die genannten Voraussetzungen erfüllt sein sollen (<ref-ruling> E. 4.2 S. 234; <ref-ruling> E. 5.1 S. 356). Bei der Rüge der offensichtlich unrichtigen Sachverhaltsfeststellung gilt das strenge Rügeprinzip (<ref-law>) und es ist demnach anhand der Erwägungen des angefochtenen Entscheids klar und detailliert darzulegen, inwiefern die vorinstanzliche Sachverhaltsfeststellung willkürlich sein soll. Demzufolge genügt es nicht, einen von den tatsächlichen Feststellungen der Vorinstanz abweichenden Sachverhalt zu behaupten. Auf solche rein appellatorische Kritik am Sachverhalt tritt das Bundesgericht nicht ein (<ref-ruling> E. 1.4.2 und 1.4.3 S. 254 f.; <ref-ruling> E. 2.2 S. 246; <ref-ruling> E. 5.1 S. 356).
Die Sachverhaltsfeststellung bzw. Beweiswürdigung erweist sich als willkürlich, wenn das Gericht Sinn und Tragweite eines Beweismittels offensichtlich verkannt hat, wenn es ohne sachlichen Grund ein wichtiges und entscheidwesentliches Beweismittel unberücksichtigt gelassen oder wenn es auf der Grundlage der festgestellten Tatsachen unhaltbare Schlussfolgerungen gezogen hat. Willkür liegt nur vor, wenn nicht bloss die Begründung eines Entscheides, sondern auch das Ergebnis unhaltbar ist. Sie ist aber nicht schon dann gegeben, wenn eine andere Lösung ebenfalls in Betracht zu ziehen oder gar vorzuziehen wäre. Dass die von Sachgerichten gezogenen Schlüsse nicht mit der eigenen Darstellung des Beschwerdeführers übereinstimmen, belegt keine Willkür (<ref-ruling> E. 2.3 S. 266; <ref-ruling> E. 3.1 S. 178; je mit Hinweisen).
2.2.3. Der Beschwerdeführer schildert anhand zahlreicher Aktenstücke seine Sicht des Sachverhalts, aus denen sich ergeben soll, dass der Zahlungsbefehl bereits am 18. Dezember 2014 zugestellt worden sei.
Er weist wiederholt auf das Zustellungszeugnis vom 4. Februar 2015 hin (das sich auf die Zustellung vom 18. Dezember 2014 bezieht; Beilage 5 zur Stellungnahme des Betreibungsamts in den Akten des Bezirksgerichts; pag. 93). Diesbezüglich hat bereits das Kantonsgericht festgehalten, dass darauf in der Rubrik "Zurückgesandte Schriftstücke" von "Atto giudiziale: precetto esecutivo" die Rede ist. Das Kantonsgericht hat ebenfalls dargelegt, weshalb es dieses Zustellungszeugnis nicht als massgeblich erachtet hat, obschon darauf von einem Zahlungsbefehl (it. precetto esecutivo) die Rede ist. Der Beschwerdeführer hält daran fest, dass da s Zustellungszeugnis vom 4. Februar 2015 von der Zustellung eines "precetto esecutivo" und nicht etwa eines "decreto di sequestro" oder ähnlichem spreche. Dies kann jedoch auf sprachliche Schwierigkeiten und mangelnde Vertrautheit mit der schweizerischen Rechtsterminologie auf Seiten der italienischen Behörden zurückgeführt werden. Einen Hinweis darauf gibt, dass das Betreibungsamt dreisprachige Formulare (für Antrag und Zeugnis) verwendet hat, die aber keinen italienischen, sondern einzig deutschen, englischen und französischen Text enthielten, während der Zustellbeamte ein viersprachiges Zustellungszeugnis verwendete, dessen Rubriken auch auf Italienisch beschriftet waren. Vor diesem Hintergrund erscheint die kantonsgerichtliche Würdigung nicht als willkürlich, zumal mit den Einwänden des Beschwerdeführers die Feststellung des Kantonsgerichts nicht entkräftet wird, dass mit dem Zustellungszeugnis vom 4. Februar 2015 eben gerade kein Zahlungsbefehl zurückgeschickt worden ist. Was der Beschwerdeführer aus den weiteren Zustellungs-, insbesondere den Postunterlagen (ebenfalls genannte Beilage 5, pag. 94 f., sowie Beilage 1 zur Beschwerde an das Kantonsgericht) ableiten will, erschliesst sich nicht, findet sich doch darin keine detailliertere Bestätigung, was für ein Schriftstück am 18. Dezember 2014 zugestellt worden ist. Nicht aussagekräftig ist der Hinweis auf den Mailverkehr zwischen dem Betreibungsamt und dem Tribunale di Verbania (vgl. oben lit. A.d; Beilage 6 des Betreibungsamts, pag. 96 ff.). Zwar ist dort ebenfalls von "precetto esecutivo" die Rede, zuweilen aber auch von "atto giudiziale" oder von Kombinationen der beiden oder ähnlicher Begriffe (z.B. "il precetto/l'atto legale"). Wenn das Kantonsgericht diesem wenig klaren Mailaustausch keinen Stellenwert beigemessen hat, ist es nicht in Willkür verfallen, zumal auch all dies die kantonsgerichtliche Feststellung nicht entkräftet, dass mit dem Zustellungszeugnis vom 4. Februar 2015 kein Zahlungsbefehl zurückgesendet worden ist.
Der Beschwerdeführer deutet sodann einen Zustellungsantrag vom 21. November 2014 des Betreibungsamts mit dem Eingangsstempel des Tribunale di Verbania, Ufficiali giudiziari, vom 29. Januar 2015 (Beilage 11 des Betreibungsamts, pag. 113) als ursprünglichen Zustellungsantrag, der aufgrund der Feiertage durch die Post erst so spät nach der Zustellung vom 18. Dezember 2014 an das Tribunale di Verbania zurückgesandt worden sei. Das Kantonsgericht sah darin hingegen nicht den ursprünglichen Zustellungsantrag, sondern den in Kopie am 28. Januar 2015 zum zweiten Mal versandten Zustellungsantrag. Damit setzt sich der Beschwerdeführer nicht auseinander, so dass darauf nicht weiter einzugehen ist.
Der Beschwerdeführer macht des Weiteren geltend, das Betreibungsamt selber habe am 17. Februar 2015 bestätigt, dass der Zahlungsbefehl am 18. Dezember 2014 zugestellt worden sei und der zurückgesandte Zahlungsbefehl am 16. Februar 2015 beim Betreibungsamt eingegangen sei (unter Hinweis auf Beilage 5 des Beschwerdeführers in den bezirksgerichtlichen Akten, pag. 37, und die Stellungnahme des Betreibungsamts, Ziff. 2.19, pag. 79). Der Beschwerdeführer übergeht, dass das Betreibungsamt diese Aussage am selben Tag noch korrigiert haben will (Ziff. 2.23 der Stellungnahme), so dass es nicht willkürlich ist, auf die vorherige Bestätigung vom 17. Februar 2015 nicht abzustellen.
Der Beschwerdeführer bezweifelt ausserdem, dass der Beschwerdegegnerin am 19. Februar 2015 ein Zahlungsbefehl zugestellt worden sei. Auf dem zweiten Zustellungszeugnis (vom 4. April 2015) sei nicht vermerkt, dass am 19. Februar 2015 ein Zahlungsbefehl zugestellt worden sei; es sei bloss von "Atto giudiziale" (recte: "Atto giudiziario") die Rede. Nach kantonsgerichtlicher Feststellung war jedoch im kantonalen Verfahren unbestritten, dass am 19. Februar 2015 tatsächlich ein Zahlungsbefehl zugestellt worden ist. Der Beschwerdeführer geht darauf nicht ein. Im Übrigen kann die Tatsache, dass das zweite Zustellungszeugnis einzig in nichtssagender Weise von einem "atto giudiziario " spricht und gerade nicht von einem "precetto esecutivo" auf die schon erwähnten sprachlichen bzw. rechtsterminologischen Schwierigkeiten zurückgeführt werden.
Der Beschwerdeführer verweist ausserdem auf das Gläubigerdoppel des Zahlungsbefehls. Beim Zahlungsbefehl, der ihm am 24. März 2015 zugestellt worden sei, könne es sich bloss um denjenigen handeln, der am 18. Dezember 2014 der Beschwerdegegnerin zugestellt worden sei, denn der zum zweiten Mal zugestellte Zahlungsbefehl sei erst am 20. April 2015 beim Betreibungsamt eingegangen (unter Hinweis auf Beilage 11 des Beschwerdeführers, pag. 46 f.). Auch dies kann die Argumentation des Kantonsgerichts nicht als willkürlich ausweisen, denn als Datum der Zustellung an die Beschwerdegegnerin ist auf diesem Zahlungsbefehl wiederum der 19. Februar 2015 angeführt. Es ist nicht ausgeschlossen, dass das Betreibungsamt das Gläubigerdoppel erstellt hat (<ref-law>), bevor es das Zustellungszeugnis mit den Unterlagen zurückerhalten hat, zumal der Rechtsvertreter der Beschwerdegegnerin bereits am 23. Februar 2015 Rechtsvorschlag erhoben hatte.
Die Beschwerde erweist sich damit als unbegründet, soweit auf sie eingetreten werden kann.
3.
Bei diesem Ausgang des Verfahrens trägt der Beschwerdeführer die Gerichtskosten (<ref-law>).

Demnach erkennt das Bundesgericht:
1.
Die Beschwerde wird abgewiesen, soweit darauf einzutreten ist.
2.
Die Gerichtskosten von Fr. 2'000.-- werden dem Beschwerdeführer auferlegt.
3.
Dieses Urteil wird den Verfahrensbeteiligten und dem Kantonsgericht Wallis, Beschwerdebehörde in Schuldbetreibung und Konkurs, schriftlich mitgeteilt.
Lausanne, 1. November 2016
Im Namen der II. zivilrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Das präsidierende Mitglied: Escher
Der Gerichtsschreiber: Zingg