Why didn't this decision occur in 2021, for example
According to themselves:
It is a statement of unequivocal support for a two-State solution - the only credible path to peace and security for Israel, for Palestine and for their peoples.
We have previously said that recognition is a step that we would ideally have taken as part of a process towards that goal.
However, we are three decades after the Oslo process and perhaps further than ever from a just, sustainable and comprehensive peace settlement.
Our decision to recognise Palestine should not have to wait indefinitely, especially when it is the right thing to do. [...]
But we cannot ignore the fact that we are taking it as Palestinians in Gaza are enduring the most appalling suffering, hardship and starvation. A humanitarian catastrophe, unimaginable to most of us and unconscionable to all, is unfolding in real time. [...]
Recognising the statehood of Palestine sends a message that there is a viable alternative to the nihilism of Hamas. [...] There is also no future in the extremist version of Zionism that fuels settler violence and illegal appropriation of land in the West Bank.
And so yes, the war appears to have been somewhat of a catalyst, in statements at least:
"The time to move from words to action has come," Sánchez told the Spanish House of Representatives. "To tell the millions of Palestinians that are suffering that we stand with them, that there's hope, and that despite the walls that are erected, the villages that are bombed and the illegal settlements that are built, the land and the identity of the Palestinians still exist."
Likewise, Norway's statement:
Recognition of Palestine is a means of supporting the moderate forces which have been losing ground in this protracted and brutal conflict. [...]
Since the Oslo Accords of roughly 30 years ago, Norway and many other countries have pursued a strategy in which recognition would follow a peace agreement. This has not been successful.
‘In the absence of a peace process and a political solution to the conflict, developments have gone in the wrong direction. Neither the Palestinian nor the Israeli people can live their lives in security. That is why we need to think differently and act accordingly. We can no longer wait for the conflict to be resolved before we recognise the state of Palestine,’ said Mr Støre.
That document even has a section titled:
Several reasons to recognise now
There are several reasons why this is the right time to recognise Palestine as a state.
‘The ongoing war in Gaza has made it abundantly clear that achieving peace and stability must be predicated on resolving the Palestinian question. The war is the lowest point in the prolonged Israeli-Palestinian conflict. The situation in the Middle East has not been this grave for many years,’ said Mr Støre.
The UN General Assembly recently adopted a resolution stating that Palestine is fully qualified for membership of the United Nations, with an overwhelming majority of 143 countries voting in favour.
‘Norway is cooperating closely with Saudi Arabia and is taking active steps to mobilise European support for the Arab peace vision. Norway and Saudi Arabia recently hosted a high-level meeting of foreign ministers in Riyadh to discuss this initiative. In a few days, Norway will be chairing an international partner meeting about Palestine in Brussels, where the new Palestinian Prime Minister and Government will be presenting their reform plans. We are hoping to make some major progress there,’ said Mr Eide.
You are also correct that opinion of Israel has dipped in many (possibly most) countries, after more than half a year of war. So, on the declarative level at least, it's a combination of that and being 'fed up' with the lack of 'day after' plans from Israel that's not just more occupation.
Of course, Israel's government disagrees and says that those countries are just "rewarding terrorism".
“The intention of several European countries to recognize a Palestinian state is a reward for terrorism,” Israeli Prime Minister Benjamin Netanyahu said in a statement.
“This would be a terrorist state. It would try to carry out the October 7 massacre again and again – and that, we shall not agree to,” he said.
“Rewarding terrorism will not bring peace and neither will it stop us from defeating Hamas.”
And Israel recalled their ambassadors from those 3 countries.
There is a somewhat interesting interview with Norway's FM in The Times of Israel containing some challenging Qs, and among them, at least one related to the timing/context:
[Q:] You paint this as a reaction to policies of the Netanyahu government. But President [Isaac] Herzog said in Davos that no Israeli in his right mind is thinking about a Palestinian state right now. [Opposition Leader Yair] Lapid doesn’t support a Palestinian state right now. [War cabinet minister Benny] Gantz doesn’t. I don’t know anyone on the Zionist political spectrum who is pushing for a Palestinian state right now. It seems like you’re going against the wishes of the Israeli public writ large, and not against this government.
[A:] Well, there was a vision back in the time of [Shimon] Peres and [Yitzhak] Rabin, of course, which then was upheld by several successive Israeli governments later.
I am fully aware of the situation right now, and I have to say that I have a lot of empathy for the psychological mood in Israel now after the horrible terrorist events on October 7. The most important thing now is to get the hostages out, which we totally support, by the way.
But I also think, as [some Israelis] have been saying, that maybe somebody has to help [them] think right now because [they] are so captured by the moment. [...]
But what we really have been reminded of is that there is no alternative to a political solution. And somebody needs to think of that.
What we’re doing now with other European countries and the Arab countries is to suggest that there is an alternative to this endless cycle of violence, and that because the endless cycle of violence ends up strengthening the more extreme forces, you see in the radicalization or the move to the right in Israel and to less believe in this, as you correctly say. But you also see the strengthening of Hezbollah, Hamas and Houthis and other Iranian agents.
And we work with people who want to limit the influence of Iran in the region, which is exactly also what the Netanyahu government wants.
But I think it’s better to do that with the Palestinians, the moderate Palestinians and the Arabs, than against them.
Regarding Spain's 'pandering' for Algerian gas [this way]... IMHO it's a somewhat plausible part of the story, but not too clear if it's likely to be successful as such. Sanchez had a fallout first with Morocco, and to 'fix' that he endorsed Morocco's plan for Western Sahara. Which in turn enraged Algeria, making them cust most of their ties with Spain, but not gas supply, reportedly due to arbitration provisions in the contracts. OTOH (despite some Spanish attempts at 'pandering' by extraditing an Islamist/dissident, who was then promptly sentenced to death) Alegeria still retaliated on the gas front by increasing exports to Italy instead! The present day result of this saga being that Spain is importing more Russian gas (LNG) than they ever did before. (OTOH this is only part of the picture, because Spain is also re-exporting said Russian gas.)
Perhaps there is something to this angle though because on 10 April 2024, "Algeria restores envoy to Madrid after two years of diplomatic dispute". (The Spanish intention to recognize Palestine had been annouced some months in advance. It was made more firm in terms of a timeline at least as early as April 2, but possibly before--I didn't do a more thorough search.)