Dusty lens. Probably pocket lint that has accumulated over the past ten years
You can try using a dust-off type product (compressed air in a can). Trying to get in there to clean it with a q-tip or similar method usually just pushes the dirt around and can make it worse.
If the cat isn't complaining about the speckled beam, you really don't have to do anything.
And all low-cost diode lasers have a rectangular beam profile (the laser chip is not round). Some of the beam may be "lost" off the edges of the round lens and make it appear elliptical or nearly round, but it actually starts out rectangular.
The effect you are referring to "graininess" in the beam is normal, it's called speckle. It is caused by interference of the waves of light hitting a surface that is not perfectly smooth.