Pretty sure the "Hello, World" got its start from the first program used in "The C Programming Language" by Kernighan and Ritchie, back in 1978. I've always presumed the foo and bar come from FUBAR[0] which seems to have originated in WWII army lingo.
Not sure about "Hello World!" besides being a cute phrase for new programs to say.
Foo Bar I would assume is from F.U.B.A.R., or F%ed Up Beyond All Repair. If so, then maybe 2 simple variables is all you can safely tweak?
No clue, really.