This question comes in two parts:
Why did Sirius move there?
I think it breaks down to a couple of reasons:
He wants to be close to Harry.
We know (and Sirius is shrewd) that Harry is in extreme danger at Hogwarts. He wants to be close to Harry, because he feels that it means he can help. He’d even relish the chance to just see Harry; bear in mind that he’s had minimal human contact for over a decade.
Would going to Hogwarts or Hogsmeade to see Harry be reckless and dangerous? Sure, but also in Sirius’s nature. In fact, he actually suggests it at one point:
And when they did not appear cheered by this, Sirius added, “When’s your next Hogsmeade weekend anyway? I was thinking, we got away with the dog disguise at the station, didn’t we? I thought I could—”
— Order of the Phoenix, chapter 14 (Percy and Padfoot)
Perhaps it’s not entirely rational to be in the cave, but you can see why he’d want to be.
Moving to Grimmauld Place is swapping out one cell for another.
After being imprisoned for twelve years, Sirius wants to spread his wings a little. In Order of the Phoenix, we see that Sirius is just miserable in Grimmauld Place. He always hated being cooped up for the Order.
The house reminds him of his vile family who threw him out, and I think he’d never return there if he could. Even without the trappings of the Order, he would still be surrounded by reminders of his family. The house makes him miserable. He’s had twelve years of that from the Dementors. Why go there voluntarily?
In fact, Harry calls this out in Order of the Phoenix:
“Yeah, he did hate [the house]!” said Harry, his voice cracking, turning his back on Dumbledore and walking away. The sun was bright inside the room now, and the eyes of all the portraits followed him as he walked, without realizing what he was doing, without seeing the office at all. “You made him stay shut up in that house and he hated it, that’s why he wanted to get out last night—”
— Order of the Phoenix, chapter 37 (The Lost Prophecy)
In Goblet of Fire, Harry makes oblique reference to Sirius “moving south”:
Harry, on the other hand, had liked them; they put him in mind of palm trees and white sand, and he hoped that, wherever Sirius was (Sirius never said, in case the letters were intercepted), he was enjoying himself. Somehow, Harry found it hard to imagine dementors surviving for long in bright sunlight; perhaps that was why Sirius had gone south.
— Goblet of Fire, chapter 2 (The Scar)
I can’t find a reference for this, but it makes sense. At the end of Prisoner of Azkaban, he writes “I believe the dementors are still searching for me, but they haven’t a hope of finding me here”. However cold that cave may be, it offers him freedom and sunshine that Grimmauld Place doesn’t.
Sirius is adventurous.
Think Padfoot the Marauder, the teenager who became an Animagus, the notorious daredevil. The last twelve years in Azkaban were torture.
He only returned to Grimmauld Place because of Dumbledore. In the meantime, I think he was thrilled to be on the run, living in the wild. Risky, but also fuelling his long-neglected sense of adventure.
Two more minor reasons that may have influenced his decision:
His parents may have warded against him.
His mother threw him out. We know from the Family Tree that she spent about six years as widow, living alone. We also know that she was a little unstable. What’s to say she didn’t ward the House against his return, the traitor that he is? The risk deters him from return.
(I'm assuming he was informed of his mother’s death in the eight years between such time and his escape. If not, he’s definitely not going home: she’d turn him in instantly.)
“Without any known magical protection” is not the same as “no magical protection”.
The protections on Grimmauld Place are necessary because it’s such a high-profile target, and in a busy city. A mountainside cave may not need such protections, and if it does, there’s nothing to say Dumbledore couldn’t take the afternoon out to lend Sirius a hand.
Why did Dumbledore describe it as the “safest place” for Sirius?
Dumbledore is smart: he’ll have figured out the above. He’ll know that Sirius would hate returning to his family home, and want to be close to Harry. So he can see why Sirius would want to avoid it, but is it safer not to?
I think so. Unlike the Dementors in Azkaban, Sirius can’t turn into a dog to avoid the demons at home. After twelve years in Azkaban, it’s amazing that he’s as mentally stable as he is. Driving him back to his family home would cause his health to spiral.
Indeed, in the final book, I think Sirius is borderline suicidal. It’s his cooped-upedness that eventually kills him, because of his mad desire to do something that drives him into danger. Living alone in that house would not be good for him. (Arguably it isn’t good for him with company, but better than if alone.)
It would not be “safe” for Sirius to return to a house that puts his health at such risk.
