With the SD250 starters (basically a rehashed 5MT starter) that the 3800's and 4.9L
Cadillacs run, if the commutator contacts get corroded (common problem) or open in any way, you will get this same situation. I had this on my my 4.9L Cad V8 do it.
As 92Bonneowner said, get a hammer, or as I did, long breaker bar in through the exhaust manifold and have someone crank it and you rap like crazy on the starter, if it starts, get the car up and on ramps to replace it ASAP. It won't last long like that. Basically if the contact is bad, turning over the starter is what helps. The solenoid gets grounded through the starter low resistance windings, so if the starter opens, the solenoid will seem bad.
A symptom of this is when warm, slower cranking, and eventually no start when hot, but restart when cold. Again, it doesn't last long at all like this. If you are over 200K, you NEED brushes! Mine at 180K were good, but my old 3800 91 Bonneville at 250K were shot and wasted the holders too, which are hard to come by.
I am a big proponet of fixing starters over replacing them with parts store rebuilts. You don't know how those were abused, so they may be under warranty, they still may be ticking time bombs to fail again. My OEM starter on mine went 180K miles and a $25 commutator replacement and $4 worth of brushes has it like new for another 180K. Beats $75 on an Autozone replacement with a 1-2 year warranty, or even a lifetime if you ask me.
You'll need to find a starter shop to get parts, no one carries them anymore. I found one, Olsen's starter in Pell Lake, WI for $25. He charges $100 to rebuild it himself. I did for $29.