Sachverhalt: A. A._ ist bei der Progrès Versicherungen AG krankenversichert. Nach einer ärztlich empfohlenen Gewichtsreduktion um 28 kg bei einer Körpergrösse von 177 cm wog er noch 90 kg. Nach der Gewichtsabnahme trat beidseits eine deutliche Brustvergrösserung (Gynäkomastie) in Erscheinung. Die Progrès Versicherungen AG, an welche sich der Allgemeinpraktiker Dr. med. C._ im Auftrag des Versicherten mit dem Gesuch um Übernahme der Kosten für eine subkutane Mastektomie beidseits (Entfernung des überschüssigen Brustgewebes) gewandt hatte, lehnte dieses Begehren nach Rücksprache mit ihrem Vertrauensarzt mit Verfügung vom 22. August 2013, bestätigt mit Einspracheentscheid vom 13. November 2013, ab. B. Die hiegegen eingereichte Beschwerde wies das Verwaltungsgericht des Kantons Graubünden mit Entscheid vom 16. Dezember 2014 ab. Das Gesuch um unentgeltliche Verbeiständung wies es ebenfalls ab. C. A._ lässt Beschwerde in öffentlich-rechtlichen Angelegenheiten führen mit den Anträgen, unter Aufhebung des vorinstanzlichen Entscheides sei der Krankenversicherer zu verpflichten, die Kosten für eine subkutane Mastektomie beidseits zu bezahlen. Eventuell sei die Sache zu neuer Beurteilung an den Krankenversicherer zurückzuweisen. Subeventuell sei die Sache zu neuer Regelung der Entschädigungsfolgen an das kantonale Gericht zurückzuweisen. Während die Progrès Versicherungen AG auf Abweisung der Beschwerde schliesst, verzichtet das Bundesamt für Sozialversicherungen auf eine Vernehmlassung.