Sachverhalt: A. A.a. A._ (Mutter) und B._ (Vater) sind die nicht verheirateten Eltern einer gemeinsamen Tochter namens C._ (geb. 2009). Die Eltern leben seit 2010 getrennt; sie sind beide sorgeberechtigt und betreuen ihre Tochter seit deren Kindergarteneintritt im August 2014 je zur Hälfte. A.b. Mit Schreiben vom 23. März 2015 teilte die Mutter der Kindes- und Erwachsenenschutzbehörde (KESB) Bern mit, sie beabsichtige den Lebensmittelpunkt nach Spanien, Provinz U._, zu verlegen. Der Vater erklärte sich mit einer Ausreise zusammen mit dem Kind nicht einverstanden. B. Mit Entscheid vom 10. Juni 2015 wies die KESB das Gesuch der Mutter um Zustimmung zum Wechsel des Aufenthaltsortes ihrer Tochter ab. Mit Entscheid vom 21. Oktober 2015 gab das Obergericht des Kantons Bern, Zivilabteilung, Kindes- und Erwachsenenschutzgericht (nachfolgend: Obergericht) der von der Mutter gegen den Kammerentscheid eingelegten Beschwerde nicht statt. C. Die Mutter (Beschwerdeführerin) hat am 26. November 2015 (Postaufgabe) gegen den obergerichtlichen Entscheid beim Bundesgericht Beschwerde in Zivilsachen erhoben. Sie beantragt sinngemäss, ihr die Ausreise mit ihrer Tochter nach Spanien (Provinz U._) zu bewilligen. Eventualiter sei die Ausreise mit Auflagen zu verbinden. Subeventualiter sei der Entscheid aufzuheben und an die Vorinstanz zurückzuweisen. Die Beschwerde richtet sich ausserdem gegen den die unentgeltliche Rechtspflege verweigernden Entscheid des Obergerichts. Die Beschwerdeführerin ersucht schliesslich um unentgeltliche Rechtspflege für das bundesgerichtliche Verfahren. D. Die KESB schliesst in ihrer Eingabe vom 25. April 2016 auf Abweisung der Beschwerde. Mit Schriftsatz vom 9. Mai 2016 beantragt der Vater (Beschwerdegegner) die Abweisung der Beschwerde. Auch er ersucht um unentgeltliche Rechtspflege für das bundesgerichtliche Verfahren. Die Beschwerdeführerin hat am 23. Mai 2016 repliziert. D._ und E._, Eltern der Beschwerdeführerin, haben sich unaufgefordert vernehmen lassen (Postaufgabe des Schreibens am 4. Juli 2016). E. Die Beschwerde wurde an der Sitzung der II. zivilrechtlichen Abteilung des Bundesgerichts vom 7. Juli 2016 öffentlich beraten und das Urteil anschliessend an die Beratung und Abstimmung mündlich eröffnet.