Why are the columns connected with VDD-KEY (basically the 5v pin)?
So they are logical HIGH by default. You can put them to LOW by setting the appropriate Arduino pin to LOW.
What are the diodes for?
That's because else the pull-downs would interconnect all row lines over ground.
I don't think it's a very clever design as your get a short if you push two buttons. You can eliminate that by changing the unused column pins to inputs and only the active column is an output but you have to ensure that by software.
I plan to use pin change interrupts to get keypresses, so during normal operation all columns would be HIGH. Is it correct that connecting two HIGH pins does not do any damage?
You don't have to put them HIGH as you have the pull-ups in place already. I would set all columns to inputs during normal operation. When you get an interrupt, you can pull one after the other to LOW (after setting it as an output) to check the column.
To answer your question: No, two high pins are the same voltage level, no current is flowing.