Would replacing Macbook's HDD to a new one speed it up?
Your key problem isn't the performance of your disk. Your key problem is the available space on your internal disk.

30 GB out 500 GB isn't enough for your kernel to breath. This is 6% of available free space.
Everytime your kernel is pageing out a page of main memory, it will waste too much time to find tiny available holes within this 30 GB.

Here is my advice:


"don't buy anything": this was a lie, please forgive me :).
If you don't have a free disk available of at least 500 GB, buy one
Clean all your cache files.
Make archives of your old files (put them on a verified external disk)
stay on step 3 until you have at least 20% free space available
(the limit to never reach on a disk is 10% free, at this limit you
will feel any search to find a free block)

If you don't have a free disk available to manage your archives,
buy one (anyway you clearly need one).

if (step 3 = OK) then


Make a full backup of your internal disk on a 500 GB external disk (Carbon Copy Cloner is the easiest way to make it a full bootable image    format).
Boot your Mac from this external disk. Verify everything is running correctly.
Fire Disk Utility and format completly your internal disk.
If this step fail, goto FAIL:.
Make the reverse operation of step 4.: bring back all your data from your external disk to your internal one
boot your Mac from this clean internal disk
fire all your applications together, and confirm everything is working fine


else

FAIL:


If it is impossible to reach this 20% of free space,
only then decide to either double your internal disk capacity
or buy you a new Mac. Considering the age of your Mac, I'd recommand this last option.


fi


To be honest, this will cost you a good day of work.