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 Art. 271 Abs. 1 Ziff. 4 SchKG 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.