This was translated in a hurry so please forgive any grammatical errors.
From the wikipedia entry:
It was first discovered in the Famicon version of "Gradius", where it was a 'full-powerup' command entered while the game is paused to give the best equipment and stats/abilities etc.
The details are as follows: When the arcade version of 'Gradius' was ported into Famicon, a junior staff had trouble with the difficulty of the game and used the command for debugging. This was published in an interview by the staff of that time, HOWEVER this was not the source of the spread of information.
Then, without removing that cheat code, they released it in the retail version. The code was then discovered in the 裏技ブーム (Trickery boom? Sorry idk how to translate this but basically there was a point of time where everyone was looking for cheat codes in various games) and became widespread.
Source: 業界技術狩人 ギョーテック、2008年12月12日放送より (If you can find a recording of the 2008/12/12 broadcast of this show, you should be able to find the full details)
About the origins of the form of the command itself (why is the code entered like this?) that is derived by the staff member involved. Apparently it is an easy-to-remember command to him.
In anticipation of the Konami Code being used in a portion of the future games, they implemented it such that normal use of the command would lead to adverse outcomes such as an instant gameover or some other negative effects. As a replacement, the game will give hints for the 'correct' command to enter.
