Why did Kohenim take off their shoes on the bimah during a certain prayer on Rosh hashana? Why did they also hold their tallit up over their heads more like tents with their arms raised?
This was birkat kohanim, the priestly blessing, which (in the diaspora, at least for Ashkenazim) is done only on the high holy days and festivals. In Israel it is done at each morning service (where a minyan is present).
This is a reflection of a temple practice. I have been taught that one reason our kohanim take their shoes off is because they did in the temple. (Although kohanim in the temple served barefoot and today's often keep their socks on.) The talmud offers other reasons to remove shoes on Sotah 40a (according to this Chabad page):
The rabbis said: "It is derived from the regulation that the kohanim are not permitted to ascend to the dukhan wearing their shoes. This is one of the ten ordinances which Rabban Yochanan ben Zakkai instituted." What is the reason? Is it not out of respect for the congregation? Rav Ashi said: "No, [the reason] there is lest a shoelace become untied and he proceeds to retie it; then people might say: 'He is the son of a divorcee.'"
"Out of respect for the congregation": because when he lifts his arms he lifts his robes, revealing his possibly-muddy shoes (were he to be wearing them). For the latter: if he stops to tie an untied shoelace, people might think he is delaying to avoid participating in the ritual because of a problem with his personal status. (A kohein is not allowed to marry a divorcee, so if his father did so that would affect him.)
The tallit is used to cover the hands because we are not supposed to look at the koheins' hands; I imagine that pulling it over the head is the easiest way to accomplish this (while still letting them move their hands freely).
You can read more about birkat kohanim at Jewish Virtual Library.