When I tried ISO 800 the sky started to come out grey. Is it still possible to "extract" the stars when the sky colour is similar to the stars themselves?
Yes. The simplest way would be to adjust Levels in a photo-editor. If you are up for a slightly steeper learning curve then IRIS (free from http://www.astrosurf.com/buil/us/iris/iris.htm
) is worth a look. You may have to experiment to see if it understands your RAW files but it can certainly work with JPEGs or TIFF files as input.
A little overexposure of the sky isn't necessarily bad as programs like IRIS can not only subtract a constant signal but they can also calculate and subtract a gradient. With your 18mm lens that will be very usefuul as the amount of background light pollution present will almost certainly vary across the frame (areas of the frame closer to the horizon have worse light pollution issues). In your case as the camera is unguided you may run into a constraint of star trails becoming an issue before the background gets too bright.
By the way, are you using that trick I mentioned to overcome the Nikon long exposure noise reduction?