If you did not feel anything, then I would worry that you were not human.
I would certainly try to find out if you can inform the "No"s through another method.
Looking at it from the applicants perspective, I find that when I have applied for a position and receive a letter in the mail, I usually know it is a "Dear John" (ie "thanks but no thanks") and am more prepared for it. Phone calls are nasty though. They usually go something like this:
"Hello, is Mac there?"
"Speaking"
"Hi, it's HRDroid1 from Company 1, how are you today?"
"Fine thanks, you?"
"Can't complain. The reason I am calling is because you attended an interview with us on Day X of Month..."
"Yes?"
"We were really impressed with your application..."
"Thankyou"
"However, I am afraid that your application was unsuccessful at this point in time..."
"Oh..."
"We will of course keep you in mind in case any other position comes up in the near future, if that is okay?"
"Sure. Thankyou."
"Have a good day"
beep... beep... beep...
Basically, there are is a good minute of buildup where you think "Have I got it" whilst the HR Drone (or employer) builds up the courage to tell you "Thanks, but no thanks".
A letter is kinder.
If the company insist on phone calls, NEVER leave them on the answering machine. That is even crueler. Preferably don't leave a message asking them to call you back either.
Get STRAIGHT to the point. I know that the small talk makes you think you are cushioning the blow, but you aren't. "Hello, is XYZ there" ... "Hello XYZ, I am calling from XYZ in response to your interview last week, unfortunately, we cannot offer you a position with our company at this time." THEN do your damage control if you wish.
Write yourself a script - it may make the chore slightly more clinical, and by extension, less personal.