Sachverhalt:
A.
Am 22. Juli 2013 erliess das Untersuchungsamt St. Gallen einen Strafbefehl wegen Hehlerei gegen X._, der dagegen Einsprache erhob. Das Kreisgericht St. Gallen verfügte am 26. September 2013, der Strafbefehl sei wegen fehlender örtlicher Zuständigkeit nicht gültig. Es wies das Verfahren zur Überweisung an die zuständige Behörde an das Untersuchungsamt St. Gallen zurück und erhob keine Kosten. Dieses überwies es an die Staatsanwaltschaft Zürich-Sihl.
Die Staatsanwaltschaft Zürich-Sihl stellte das Verfahren am 4. Februar 2014 ein. Sie nahm die Verfahrenskosten auf die Staatskasse und richtete X._ weder eine Entschädigung noch eine Genugtuung aus. Dagegen erhob X._ Beschwerde.
Das Obergericht des Kantons Zürich trat mangels Zuständigkeit nicht auf die Beschwerde von X._ ein. Sein Gesuch um "unentgeltliche Rechtspflege und Verbeiständung" wies es ab, soweit es darauf eintrat, und auferlegte ihm die Gerichtsgebühr.
B.
X._ beantragt mit Beschwerde in Strafsachen, die Verfügung des Obergerichts sei aufzuheben und die Sache zu neuer Entscheidung an dieses zurückzuweisen. Er ersucht um unentgeltliche Rechtspflege und Verbeiständung.
C.
Das Obergericht und die Oberstaatsanwaltschaft des Kantons Zürich haben auf eine Stellungnahme verzichtet.

Erwägungen:
1.
1.1. Der Beschwerdeführer rügt im Wesentlichen, indem die Vorinstanz auf seine Beschwerde nicht eingetreten sei, verletze sie die Rechtsweggarantie von <ref-law>. Sie verwehre ihm eine Beurteilung der Einstellungsverfügung, obwohl dies in <ref-law> vorgesehen sei. Da vorliegend die Einstellungsverfügung einer zürcherischen Staatsanwaltschaft zu prüfen sei, könne es an der Zuständigkeit der Vorinstanz als kantonale Beschwerdeinstanz keinen Zweifel geben. Zudem habe er bei der Vorinstanz vorgebracht, der Erlass der Einstellungsverfügung ohne vorgängige Parteianzeige gemäss <ref-law> verletze seinen Anspruch auf rechtliches Gehör. Bereits dieser Verfahrensmangel hätte die Aufhebung der Verfügung zur Folge haben müssen. Zumindest hätte die Vorinstanz die Verletzung des rechtlichen Gehörs aber bei der Kostenauferlegung berücksichtigen müssen (Beschwerde S. 6 ff.).
1.2. Die Vorinstanz erwägt, werde das Verfahren eingestellt, so habe die beschuldigte Person grundsätzlich Anspruch auf eine Entschädigung ihrer Aufwendungen für die angemessene Ausübung ihrer Verfahrensrechte (<ref-law>). Werde ein Verfahren in einem Kanton eröffnet und an einen anderen Kanton abgetreten respektive in einem anderen Kanton eingestellt, so sei in analoger Anwendung von <ref-law> der Kanton entschädigungspflichtig, in dem das Strafverfahren eingeleitet worden sei. Dies rechtfertige sich vorliegend umso mehr, als der örtlich offensichtlich unzuständige Kanton St. Gallen einen Strafbefehl erlassen habe, der Anlass zur Einsprache gegeben und auch materiell einer Prüfung nicht standgehalten habe. Das Strafverfahren gegen den Beschwerdeführer sei im Kanton St. Gallen eingeleitet worden. Daher habe der Beschwerdeführer die von ihm verlangte Entschädigung in diesem Kanton geltend zu machen. Auf die Beschwerde sei somit mangels Zuständigkeit nicht einzutreten (Verfügung S. 2 f. E. 4.1-4.3).
1.3.
1.3.1. Gemäss <ref-law> hat jede Person bei Rechtsstreitigkeiten Anspruch auf Beurteilung durch eine richterliche Behörde. Bund und Kantone können durch Gesetz die richterliche Beurteilung in Ausnahmefällen ausschliessen.
1.3.2. Nach <ref-law> legt die Strafbehörde im Endentscheid die Kostenfolgen fest. Sie kann diese Festlegung vorwegnehmen, namentlich in Zwischenentscheiden oder Entscheiden über die teilweise Einstellung des Verfahrens (<ref-law>).
Nach <ref-law> werden die Verfahrenskosten des Strafprozesses vom Bund oder dem Kanton getragen, der das Verfahren geführt hat; abweichende Bestimmungen der StPO bleiben vorbehalten. Wird das Verfahren gegen die beschuldigte Person eingestellt, so hat sie gemäss <ref-law> Anspruch auf Entschädigung ihrer Aufwendungen für die angemessene Ausübung ihrer Verfahrensrechte. Die Strafbehörde prüft den Anspruch von Amtes wegen (<ref-law>). Der Staat übernimmt die entsprechenden Kosten nur, wenn der Beistand angesichts der tatsächlichen oder rechtlichen Komplexität notwendig und der Arbeitsaufwand des Anwalts gerechtfertigt waren. Ein Anspruch auf Entschädigung für Verteidigungskosten gestützt auf <ref-law> besteht nicht nur in den Fällen der notwendigen Verteidigung im Sinne von <ref-law> oder in den Fällen, in denen bei Mittellosigkeit der beschuldigten Person gestützt auf <ref-law> eine amtliche Verteidigung hätte angeordnet werden müssen, weil dies zur Wahrung der Interessen der beschuldigten Person geboten gewesen wäre. Der Beizug eines Wahlverteidigers kann sich als angemessene Ausübung der Verfahrensrechte erweisen, auch wenn er nicht als geradezu geboten erscheint (<ref-ruling> E. 2.3.3). Beim Entscheid über die Angemessenheit des Beizugs eines Anwalts sind neben der Schwere des Tatvorwurfs und der tatsächlichen sowie rechtlichen Komplexität des Falls insbesondere auch die Dauer des Verfahrens und dessen Auswirkungen auf die persönlichen sowie beruflichen Verhältnisse der beschuldigten Person zu berücksichtigen (a.a.O. E. 2.3.5 S. 203).
1.3.3. Das rechtliche Gehör dient der Sachaufklärung und stellt ein persönlichkeitsbezogenes Mitwirkungsrecht beim Erlass eines Entscheids dar, welcher in die Rechtsstellung des Einzelnen eingreift. Dazu gehört insbesondere das Recht des Betroffenen, sich vor Erlass eines solchen Entscheids zur Sache zu äussern, erhebliche Beweise beizubringen, Einsicht in die Akten zu nehmen, mit erheblichen Beweisanträgen gehört zu werden und an der Erhebung wesentlicher Beweise entweder mitzuwirken oder sich zumindest zum Beweisergebnis zu äussern, wenn dieses geeignet ist, den Entscheid zu beeinflussen (<ref-ruling> E. 5.1 mit Hinweisen).
1.4. Indem die Vorinstanz mit der Begründung, sie sei nicht zuständig, auf die Beschwerde des Beschwerdeführers nicht eintrat, verletzt sie <ref-law> und die Rechtsweggarantie nach <ref-law>. Sie war offensichtlich zuständig für seine Beschwerde gegen die Einstellungsverfügung der Staatsanwaltschaft Zürich-Sihl (vgl. Art. 20 Abs. 1 lit. b und Art. 393 Abs. 1 lit. a StPO i.V.m. § 49 des Gesetzes über die Gerichts- und Behördenorganisation im Zivil- und Strafprozess vom 10. Mai 2010 [GOG/ZH]). Die Vorinstanz vertritt die Auffassung, der Beschwerdeführer hätte die Entschädigung im Kanton St. Gallen geltend machen müssen, weil das Strafverfahren da zu Unrecht eingeleitet wurde. Dabei scheint sie aber die Fragen, ob eine Entschädigungspflicht besteht, welchen Kanton diese gegebenenfalls trifft und ob eine Überwälzung der geleisteten Entschädigung an einen anderen Kanton möglich ist, mit der Frage zu vermengen, wer diese zu prüfen und darüber zu entscheiden hat. Soweit die Vorinstanz dem Beschwerdeführer sinngemäss vorwirft, er hätte sich gegen den Entscheid des Kreisgerichts St. Gallen wenden müssen, scheint sie zu verkennen, dass dieses zwar die Kosten regelt, sich aber nicht zu einem Entschädigungsanspruch des Beschwerdeführers äussert. Dazu war es bei der Ausfällung seines Entscheids, der das Verfahren nicht erledigte, auch nicht verpflichtet (vgl. <ref-law>).
1.5. Selbst wenn der Argumentation der Vorinstanz gefolgt werden könnte, verletzt sie den Anspruch des Beschwerdeführers auf rechtliches Gehör, indem sie auch seine weiteren Rügen gegen die Einstellungsverfügung nicht behandelt. Ob <ref-law> und <ref-law> verletzt sind, weil ihm die Einstellungsverfügung persönlich zugestellt und der Verfahrensabschluss vorgängig nicht angekündigt wurde (vorinstanzliche Akten, act. 2 S. 5), ist nicht abhängig von der Frage einer allfälligen Entschädigung.
2.
Die Beschwerde ist gutzuheissen. Die angefochtene Verfügung ist aufzuheben, und die Sache ist zur neuen Entscheidung an die Vorinstanz zurückzuweisen.
Es sind keine Kosten zu erheben (Art. 66 Abs. 1 und 4 BGG). Das Gesuch um unentgeltliche Rechtspflege wird gegenstandslos. Der Kanton Zürich hat den Beschwerdeführer für das bundesgerichtliche Verfahren angemessen zu entschädigen (Art. 68 Abs. 1 und 2 BGG). Die Entschädigung ist praxisgemäss dem Rechtsvertreter auszurichten.

Demnach erkennt das Bundesgericht:
1.
Die Beschwerde wird gutgeheissen. Die Verfügung des Obergerichts des Kantons Zürich vom 22. April 2014 wird aufgehoben, und die Sache zur neuen Entscheidung an die Vorinstanz zurückgewiesen.
2.
Es werden keine Kosten erhoben.
3.
Der Kanton Zürich hat dem Vertreter des Beschwerdeführers, Rechtsanwalt Andreas Fäh, eine Entschädigung von Fr. 3'000.-- auszurichten.
4.
Dieses Urteil wird den Parteien und dem Obergericht des Kantons Zürich, III. Strafkammer, schriftlich mitgeteilt.
Lausanne, 27. Oktober 2014
Im Namen der Strafrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Mathys
Die Gerichtsschreiberin: Pasquini