There is a 'track' leading north from El Fasher to Kufra via Uweinat. It is definitely not a route you should attempt alone, it's a good 1500 kilometres without fuel/water. To my knowledge, there are truck convoys passing each way twice a week, you should join one of those.
Up till recently the crossing was only permitted to Libyans & Sudanese, but recently travelers have been permitted to continue legally from Kufra to Sudan - I don't know if this is true in reverse. You definitely need to get confirmation when you receive your Libyan visa.
Other than bureucratic difficulties, and the long stretch, the track itself is quite easy, no major obstacles along it's course (though quite soft for most of the way in the upper Sudan - expect doubled fuel consumption!). There are definitely no mines along that way.
I've heared (but have no firsthand info) that the security situation in the Kordofan is quite bad, especially around Mellit north of El Fasher, but then again there have been no reports of any travelers being harmed.