Steve, I know jack about Photoshop. But, I'm sure it has many of the same features as some of the paint programs I use. One can "pick" a background color and paint one pixel at a time. I was thinking maybe "pick" your background color, then use a pencil tool to paint those pixels surrounding each star that give it an oblong form.
Another option might be to size a pencil, or whatever tool can make a small circular spot, completely cover over a star, then re-paint it the appropriate size (and color, even.)
As for taking a scanned nebula, yea, would have to experiment with that one. You might be able to "spray" paint some pixels of either background color or nebula color of varying saturation to get a nice re-touching effect.
When you're done, you might even invert the colors, background becomes nearly black with a brighter nebula within it. Again, color is an option. You can get some pretty soft hues.
I do planets, but here's an idea of what PC paint can do. Maybe even touching up scans of pencil sketches. In effect, you'd be using the original scan to re-create a "painted" version, if that's what you want to do in terms of saturation, hue, rounding out the stars, and maybe softening the nebula.
Otherwise, just making the stars round might simply require single pixel manipulation with the background color. If you make a mistake, just "undo."