To check if the C compiler did install, get a prompt (xterm fine), and use:
$gcc --help
If you get multiple lines of help output, the install is fine.
There are other ways to install the compiler, manually for example.
But your problem looks like some kernel problem to me, since there's being complained about missing kernel-headers.
In any case, I'm more than 90% sure you shouldn't reinstall the whole OS, I think you just have to 'reyum' a package called something like kernel-headers (but I don't know exactly what yum is, and know less about Fedora than you).
Manually installation requires to goto
http://gcc.gnu.org/
Download the source code, unpack it, configure it, compile it, install it in the right place (not much work, but greater hassle than use of packages).