One thing I'd try is simply to run Disk Utility - preferably rebooting from your Mac's recovery partition - to see if there's anything wrong with the drive or the data that's on the drive. Partition map problems and other issues can slow the system down.
If it's feasible, it may even be a good idea to back up, reformat the drive, then restore (again, Recovery Partition, paired with a Time Machine backup, should be all you need).
I agree with the SSD advice, just on general principle. I've done that upgrade myself now twice - once on a late 2009 MacBook (white polycarbonate) and on a 2008 Mac Pro. In both cases, performance improved dramatically. It was a night and day difference. You don't realize how performance-constrained a Mac is by the hard drive until you replace it with SSD.
But in both cases, the SSD upgrade was made pre-Mavericks. I'm not aware of anything in Mavericks that would explain a dramatic slowdown post-upgrade, especially now that you've improved RAM.