What does fasting do? Is it to put us in a certain mindset? If so how does it do so? Does the pain itself atone? If so how and why? Or is it some other reason?
Fasting allows introspection. When you are well fed you are all-too-aware of yourself. When you step back from physical pleasures you can focus more sincerely on repentance, or on the solemn ideas of the day. (But pain is a distraction, which is why it is important to prepare well for the fast.)
Additionally, fasting is a form of self sacrifice. Medieval sefarim suggest a person fasts whenever he does teshuva.
About Yom Kippur, the Maharal writes that the soul dwells completely in the body through the five enjoyments. These make the body match up to a soul through being a place of life, unique, wholesome, clean and aloof. These are attributes of the soul which has five names accordingly: נפש, רוח, נשמה, יחידה, חיה.
By refraining from these enjoyments, the soul is a bit removed from the body. This is appropriate for a day in which the soul is cleansed from sins of which the body dragged it into.
In his excellent book “Teshuvah” Rabbi Immanuel Bernstein, suggests that the translation of וְעִנִּיתֶ֖ם אֶת־נַפְשֹֽׁתֵיכֶ֑ם is not to “afflict” but to “unsettle”. He derives this from the fact that the amount of food which would cause punishment is not an olive's bulk as elsewhere but a fat date which is more. Chazal understood that the amount of the fat date is sufficient to settle one's mind.
Being unsettled physically is likely to lead to a more productive form of introspection.
(similar answer to that of HaLeiVi)
As most of our sins come from our physical urges, it makes sense to withhold from physical pleasures when one tries to atone.
Besides fasting, there are also sex, bathing, and leather footwear (that's what the Sages ruled). The difference is that fasting is explicit in the Torah and all others fall under Rabbinical definition of עינוי - types of affliction.
—— PS: THere's a dispute in the Gemmarah if the Miztvot have reasons or not, anyway, fasting on YK is explicitly forbidden in the Torah so we have to fast even if no reason makes sense to us, just because G-d commanded us so.