New HDD required?

My Macbook pro (mid 2012) recently stopped booting up - it's unable to get past a grey screen with a loading bar (normally gets to the end of the loading bar, then turns off). I took it to a local Mac specialist, who found no problems in their diagnostics and informed me they're unable to repair it as it's just "slowed down with age".

I disagreed, so did some internet digging - I ran the fsck -fy command when booting it up, and got the following: "Incorrect number of thread records", "incorrect number of extended attributes" and finally "The volume Macintosh HD could not be repaired after 3 attempts". I've tried a couple of times - same error each time.

Couple of questions:

1. Some investigation suggests this means the HD is knackered and won't be repairable - is this right?

2. I'm not averse to replacing the HD (I'd use an SSD). I've got a recent time machine back-up. I won't be able to clone the existing disk image - what's the best way to install the OS on a new SSD and then subsequently use time machine to move files across?

Thoughts/suggestions welcome!

Cheers

Matt