I'm still gathering information. I talked to a friend who keeps pretty good track of these things, and he says that "old school" rappers who were known to wear kufiyas include Stetsasonic, EPMD, and Paris. I've not yet found any photographic evidence, but Paris makes intuitive sense, given his militant, Black Pantherish politics. Stetsasonic were conscious rappers, from NYC, where kufiyas were very common in the 1980s, so it's possible. EPMD? From NYC, so again, possible, although not as convincing as Stetsasonic to my mind.
The back cover of King Sun's 1990 album, Righteous But Ruthless, shows Sun sporting an all-black kufiya--definitely not a "Palestinian" style one. (The guy standing next to him--possibly producer King Shameek--is wearing a fez/tarboush.) King Sun never made a big impact, but was one of many influential rappers of the late eighties and early nineties who belonged to the Nation of Gods and Earths (Five Percenters.)
Method Man (of the Wu Tang Klan) reportedly appeared in a kufiya in a video (but not "PLO Style, as I would have guessed.) I'm still trying to find which one. He also reportedly wrapped himself in a Palestinian flag in concert. Mos Def has worn a kufiya in concert as well, and has performed at benefits for Palestinian causes. (Mos Def is a "conscious rapper" as well as a Sunni Muslim--as opposed to belonging to the Nation of Islam or the Nation of Gods and Earths.)
And another Lupe spotting--an old one, from the cover of XXL (last October):