Sachverhalt: A. Die Staatsanwaltschaft Graubünden eröffnete am 3. Februar 2012 gegen X._ eine Strafuntersuchung wegen einfacher und grober Verletzung von Verkehrsregeln. Am 12. März 2013 übermittelte sie die Verfahrensakten dem Bezirksgericht Moesa. Dieses führte am 16. Oktober 2013 eine erste Hauptverhandlung durch, sistierte das Verfahren und wies die Anklageschrift zur Ergänzung bzw. Berichtigung an die Staatsanwaltschaft zurück. Die Staatsanwaltschaft reichte dem Gericht am 31. Oktober 2013 die bereinigte Anklageschrift ein. Das Bezirksgericht Moesa verurteilte X._ am 16. September 2014 wegen grober und einfacher Verletzung von Verkehrsregeln zu einer bedingt vollziehbaren Geldstrafe von 30 Tagessätzen zu je Fr. 470.-- sowie zu einer Busse von Fr. 2'800.-- und auferlegte ihm die Verfahrenskosten. B. Das Kantonsgericht von Graubünden hiess die Berufung von X._ am 29. April 2015 teilweise gut. Es sprach ihn vom Vorwurf der groben Verletzung von Verkehrsregeln im Sinne von Art. 35 Abs. 2 i.V.m. Art. 90 Abs. 2 SVG und der Verletzung von Verkehrsregeln im Sinne von Art. 34 Abs. 4 SVG sowie Art. 12 Abs. 1 der Verkehrsregelnverordnung vom 13. November 1962 (VRV; SR 741.11) i.V.m. Art. 90 Abs. 1 SVG frei. Es erklärte ihn der Verletzung von Verkehrsregeln gemäss Art. 29 Abs. 1 VRV i.V.m. Art. 90 Abs. 1 SVG und der groben Verletzung von Verkehrsregeln gemäss Art. 34 Abs. 2 und Art. 35 Abs. 4 i.V.m. Art. 90 Abs. 2 SVG für schuldig. Es bestrafte ihn mit einer bedingt vollziehbaren Geldstrafe von 20 Tagessätzen zu je Fr. 300.-- und einer Busse von Fr. 1'240.--. Es auferlegte ihm 40 % der erstinstanzlichen und 2/3 der zweitinstanzlichen Kosten. Es sprach ihm für das erstinstanzliche Verfahren bzw. das Berufungsverfahren eine Entschädigung von Fr. 8'878.20 bzw. von Fr. 2'180.90 zu. Das Kantonsgericht hält in Bezug auf den Schuldspruch der groben Verletzung von Verkehrsregeln folgenden Sachverhalt für erwiesen: X._ fuhr am 1. Oktober 2011 um 14.10 Uhr mit seinem Personenwagen aus dem San Bernardino-Tunnel in Richtung Viadukt "Isola". Auf der Höhe der Vorsignalisation "San Bernardino 1000 m" (für den nordwärts fahrenden Verkehr) überholte er in der unübersichtlichen Rechtskurve das von A.A._ gelenkte Fahrzeug. Dabei überfuhr er eine Sicherheitslinie. C. X._ beantragt mit Beschwerde in Strafsachen, Ziff. 2, soweit er der groben Verletzung von Verkehrsregeln für schuldig befunden worden sei, Ziff. 3, 5, 6 lit. a und b sowie 7 des Urteils des Kantonsgerichts Graubünden seien aufzuheben. Er sei vom Vorwurf der groben Verletzung von Verkehrsregeln freizusprechen. Im Zusammenhang mit dem Schuldspruch der Verletzung von Verkehrsregeln gemäss Art. 29 Abs. 1 VRV i.V.m. Art. 90 Abs. 1 SVG sei er mit einer Busse von Fr. 40.-- zu bestrafen. Die Kosten der Staatsanwaltschaft Graubünden von Fr. 2'350.-- seien auf die Staatskasse zu nehmen bzw. dem Kanton Graubünden zu überbinden. Im Falle der Abweisung seines ersten Rechtsbegehrens seien diese Kosten im Umfang von mindestens Fr. 1'000.-- dem Kanton Graubünden aufzuerlegen, eventualiter sei die Sache zur Neuverteilung der Kosten der Staatsanwaltschaft an das Kantonsgericht zurückzuweisen. Die Kosten des Bezirksgerichts Moesa und des Berufungsverfahrens seien vollumfänglich dem Kanton Graubünden/der Staatskasse zu überbinden. Für das Verfahren vor der Staatsanwaltschaft Graubünden und dem Bezirksgericht Moesa sei ihm eine Parteientschädigung von Fr. 14'797.10 bzw. für das Berufungsverfahren eine von Fr. 6'542.70 zuzusprechen. Eventualiter sei die Sache zu neuem Entscheid an die Vorinstanz, subeventualiter an die erste Instanz zurückzuweisen. Der Beschwerde sei die aufschiebende Wirkung zu erteilen. D. Die Staatsanwaltschaft und das Kantonsgericht von Graubünden beantragen die Abweisung der Beschwerde. X._ verzichtet auf eine Replik.