The Leket Yosher (pg. 118) explains, that the reason we start selichos on motzei Shabbos, is because it is the closest time to Shabbos, and on Shabbos most people learn Torah, as they are not occupied with work. Since people learn on Shabbos, they are happy, as when one fulfills the mitzvah of Talmud Torah he becomes very happy. Moreover, people fulfill the mitzvah of oneg Shabbos, and are in a good mood. Chazal say (Shabbos 30b) that the Shechinah only rests on those who are happy with the fulfillment of mitzvos. Therefore, motzei Shabbos is the optimum time to start selichos.
Based on the above, we may add, that one should make sure to increase in learning Torah on the Shabbos before starting selichos. One who does the above, will then be able to say: "Listen to our Torah and our tefillah." First Hashem listens to rinah which is Torah (see Vayikra Rabbah 19:1 and Rambam Talmud Torah 3:13) then He listens to tefillah which is selichos.
Due to the above, the kadmonim established that first night selichos starts on motzei Shabbos and we even mention "At the conclusion of resting". Although normally, the Rema writes that selichos should be recited early in the morning, on the first day many people say it at night, as we want it to be as close to Shabbos as possible.
