Why is setup() executed twice at runtime?
It isn't, it's displaying the previous message from when you didn't have the Serial Monitor open yet, plus the new message caused by the Arduino resetting from the Serial Monitor being opened.

If you put a longer message in there you'll probably see the first line get cut off and then the full line.