They're both Namekians
Kami and "King Piccolo" are the same type of entity; a Namekian. Kami expelled the evil inside of himself, so he could better become the protector of earth. Both Kami and King Piccolo have lost some of their memories, which is why their origin story changes slightly throughout the series as more is revealed. Due to his memory loss and war-filled upbringing, King Piccolo, assumes the title of Demon as he acts like one towards the citizens of earth.
To further prove they are both the same species, Piccolo Jr., the Piccolo of the later Dragonball episodes and the DBZ series, goes to Namek during the Frieza saga, and is able to absorb other Namekians into himself, increasing his power, as any other Namekian would. Later, he also fuses with Kami himself in the late Android/early Cell saga, gaining power greater then a Super Sayain.
This is the scene of Kami expelling the evil inside of him, which becomes King Piccolo.
The Nameless Namekian is the only Namekian in the entire series shown to perform this, but there are two different and conflicting versions of the event. In Dragon Ball episode 125, "Earth's Guardian Emerges", the Nameless Namekian was portrayed as consciously expelling a black ghost-like apparition (presumed to be King Piccolo). But later, in Dragon Ball Z episode 54, "Guru's Gift", when Grand Elder Guru probes Krillin's mind he sees the Nameless Namekian suddenly falling out of bed and onto the floor, at which point King Piccolo tears away from his body, making the divided beings. One explanation to these conflicting versions is that the original flashback was actually an event from within the Nameless Namekian's subconscious, since he appeared to have been sleeping during the start of Guru's vision, which is usually the more well known of the two scenes.