Does a pulldown resistor use less battery power than a pullup resistor?
The input current does not depend on the pin level. Have a look at this discussion from avrfreaks. The input impedance of a digital pin is extremely high. The leakage current of the Atmega328P (here as example chip) is mentioned to be 1uA for both pin states. So this current is both unavoidable and neglectable from a normal view.

But the input impedance of a digital input pin is not only dependent on this leakage current. There is also a capacitance, which will lower the impedance for higher frequencies. So, if you drive the input with higher frequencies, the input will draw more current. But you only have a switch connected to it, which is very very low frequency.

So it doesn't matter, if you pullup or pulldown. The main current consumption will result from the moments, where the switch is activated, since then a current flows through the pullup/pulldown resistor to ground.


  Tangentially, should there be a resistor on the connection to Vcc as well?


No need for a resistor there. The input impedance of the pin is already high enough and you don't want to create a voltage divider with your pulldown resistor (which would change the voltage levels at the pin).