US nuclear-powered submarines use highly-enriched uranium (HEU) as their power source. (The UK ones also use HEU, sourced from the US, but processed locally into cores.) So, critics say/claim HEU-powered submarines are similar enough to a floating dirty bomb, which they don't want entering their waters. See for example this complaint/claim from a NZ group.
“If we allowed any nuclear submarine into Auckland or Wellington Harbours a nuclear accident resulting from collision, grounding, fire, explosion or reactor leaks could have dire consequences for human and marine life and jeopardise shipping, fishing, recreation and other marine based activities for generations.”
“Another concern is that the nuclear reactors in the submarines to be acquired by Australia use highly enriched uranium (HEU) rather than low-enriched uranium (LEU) - the normal fuel for nuclear reactors. HEU is the principal material required to make a nuclear bomb. [...]
And even some Australian groups opposing the deal say something similar, albeit in terms of risk of pre-emptive attack, besides accidents:
The Nobel Peace Prize-winning International Campaign to Abolish Nuclear Weapons (ICAN), Australia tweeted about the deal: “The nuclear-powered submarine deal raises serious concerns over nuclear proliferation as the UK and US’ models use highly enriched uranium.
“This is not prestige, this is provocation.”
“Important questions remain over construction of the submarines and the potential imposition of military nuclear reactors on Adelaide or other cities, making construction sites and host ports certain nuclear targets,” said Gem Romuld, Director of ICAN Australia.
“Military nuclear reactors in Australia would present a clear nuclear weapons proliferation risk and become potential sites for nuclear accidents and radiological contamination long into the future.”
Green Party leader Adam Bandt even likened the move to putting “floating Chernobyls in the heart of Australia’s cities”.
He said it makes “Australia less safe”.
NZ has maintained a long-term policy of not allowing nuclear-powered vessels (HEU or otherwise) from entering its waters:
"New Zealand's position in relation to the prohibition of nuclear-powered vessels in our waters remains unchanged," Ardern said.
The ban was introduced in the wake of French nuclear testing in the Pacific and led to the US navy banning its warships from entering New Zealand ports for more than 30 years.
The destroyer USS Sampson visited in late 2016 but only after the then-prime minister John Key gave a special exemption, saying he was "100 percent confident" the vessel was not nuclear powered or carrying nuclear weapons.
(Based on DVs) you may think this is bollocks and nonsense, but the uniform treatment of the nuclear-powered and nuclear-armed vessels has been a long standing policy of the Labour party in NZ, since back in 1985.
[PM David] Lange sought to soften Labour Party policy on this issue but found little room to move; party activists were unwilling to draw distinctions between nuclear propulsion and nuclear weapons.
I'm not sure if the Labour party itself has articulated the 'why' angle on nuclear-powered in anymore detail, so I gave you some NZ NGO's take further above, why they fear/oppose HEU-powered in particular.
Interestingly though, concerns about naval reactor designs were voiced (by NZ) back in the 1970s as well:
concerns about the safety of nuclear-powered ships first emerged on the political agenda. In 1972, Labour Prime Minister Norman Kirk declined the application of an American nuclear-powered submarine to visit New Zealand based on safety concerns. New Zealand had requested technical details of the reactor which the United States had refused to give. Moreover, neither the United States nor the United Kingdom were willing to pay compensation to New Zealand if one of their visiting ships had an accident in port. Thus, this was not a move to prohibit nuclear-powered ship visits. Kirk was only pushing for a declaration of full liability to be paid by the American or British government in case of accident. In fact, a number of other countries including Australia had imposed similar restrictions on nuclear-powered
ship visits on the same grounds. In 1974, the U.S. gave New Zealand ‘an absolute guarantee of liability for any nuclear reactor accident’ and the United Kingdom followed suit in 1976. Although visits by nuclear-propelled warships did not take place between 1971 and 1976, conventionally-powered ship visits still occurred.
The National Government under Robert Muldoon allowed for the resumption of visits by nuclear-propelled vessels in 1976.
As visits increased under Muldoon (and based on declassified cables, mostly due to his government's requests than any needs of the US) there was political backlash... but this initially did not have nuclear-power in its sights, although that came about in 1983
Richard Prebble’s first attempt to introduce an antinuclear legislation into Parliament. In 1976, he called ‘for the recognition of the South Pacific nuclear-free zone.’ After failing to get a majority in Parliament, Prebble made a second attempt in 1982, this time with the Nuclear Free Zone (New Zealand) Bill. He pointed out that ‘his bill would not ban visits of nuclear-powered
ships ... It dealt solely with whether parliamentarians were prepared to allow nuclear weapons to be brought into New Zealand.’ This bill was equally unsuccessful. One year later, on 3 August 1983, Bruce Beetham, leader of the Social Credit League, attempted to introduce the Prohibition of Nuclear Vessels and Weapons Bill. As Beetham stated,
although expensive to build, nuclear powered ships do not need constant refueling, and for that reason they are ideal vehicles for the offensive role that falls to the Navy. That being so, such vessels will almost invariably—in fact, one could almost say automatically—be armed with offensive weapons, which must include nuclear weapons.
Thus, Beetham’s bill was the first attempt to introduce a ban on nuclear-powered ships to parliament because such ships were almost certainly armed with nuclear weapons. In the end, the bill was defeated by 40 to 39 votes.
The following year, Richard Prebble launched his third attempt to make New Zealand nuclear-free. On 12 June 1984, Prebble introduced the Nuclear Free New Zealand Bill. This time, also Prebble’s bill called for the exclusion of nuclear-powered ships from New Zealand. As Prebble explained, the bill ‘prohibits the entry of nuclear powered ships and nuclear weapons into New Zealand and further prohibits the building of nuclear reactors within New Zealand.’ Prebble almost succeeded to introduce this bill because National Party MP Marilyn Waring threatened
Prime Minister Muldoon to cross the floor and vote for Prebble’s bill against her own party caucus. As a result, National Party MPs prevented Waring from speaking in Parliament that day by raising numerous points of order until Waring’s time to speak had expired. On the following day, Prebble’s bill was defeated by 40 to 39 votes just like Beetham’s bill one year earlier. Nevertheless, Waring did vote for the bill together with her colleague Mike Minogue. Prebble’s bill was
only defeated because two alienated Labour MPs had voted with the government.
So NZ really came just one vote short of banning nuclear reactors on its soil as well, during that era. (After a snap election, which saw Lange become PM, the Bill amended again to not mention soil-based reactors anymore, passed 42 to 30.)
From the same source, the NZ right wing (such as the ACT party) contends however that the ban on nuclear propulsion made/makes no sense and it's simply a convenient cover for anti-American sentiments within the left. Some Labour MPs that in the meantime have defected to ACT but were privy to the discussions within Labour at the time (such as Ken Shirley) assert this.
After the Cold War ended and the US declared in 1992 that its surface ship won't carry nuclear weapons on port visits, under PM Jim Bolger (of the National party), NZ ordered a review of the law section (11) of the Bill that bans nuclear propulsion in particular. The [Somers] commission appointed for this was attacked in the left-wing press even as its proceedings were underway, since some of its members were well-known supporters of admitting nuclear-powered ships. So its (predictable) final report didn't really change any minds and Bolger gave up on the idea of changing the law, apparently without putting it to a vote. Some have even commented (there are ample quotes in that thesis) that given the political capital invested by New Zealanders in confrontation with Washington, the ban (on nuclear propulsion) had acquired symbolic importance, and giving it up meant tarnishing New Zealand's image as nuclear-free and was seen as a capitulation to US demands. Others opponents insisted on the safety angle, contending that it wasn't good enough.
There was apparently another attempt in 2005 by the ACT party to have the ban on propulsion rescinded (which isn't covered in that thesis), apparently also without success. According to Wikipedia
John Key promised in 2006, just after being elected leader of the National Party, that "the nuclear-free legislation will remain intact" for as long as he is the leader of the National Party.
Keys was PM from 2008 to 2016.
The Malaysian objection doesn't seem incredibly specific, other than pointing to an arms race. Perhaps vying to be a regional power, Malaysia feels like it would be forced to increase its own navy spending to keep up with the improved Australian one and likely Chinese response. As Reuters commented:
"It will provoke other powers to also act more aggressively in the region, especially in the South China Sea," Malaysia's Prime Minister Office said in a statement.
The statement did not mention China, but Beijing's foreign policy in the region has been increasingly assertive, particularly its maritime claims in the resource-rich South China Sea, some of which conflict with Malaysia's own claims.
Malaysia only has two submarines (and they plan to have 4 ... by 2050); that's fewer than even its much smaller neighbor, Singapore. So Malaysia probably doesn't feel too good about others in the region getting even farther ahead of them, in this department.
They also reference ZOPFAN, which seems to be some kind of non-aligned movement treaty, so perhaps Malaysia is also resenting more involvement of the Western powers, but I'm not too sure about that. Actually, digging up more material on ZOPFAN, that seems to be the case:
ZOPFAN, the Zone of Peace, Freedom and Neutrality in Southeast Asia, was another Malaysian initiative, advanced at a time when Britain had withdrawn the bulk of its forces from the region and the United States had begun to come to terms with the People's Republic of China. The archives in Wellington, like those in London, help to document the concept. Tun Ismail, former Minister of Home Affairs and advocate of regional association, had in fact presented the idea in a debate on defence in the Dewan Rakyat back in January 1968, his aim being to save money that could be spent on social services. “The time is … ripe for the countries in the region to declare collectively the neutralization of South-East Asia. To be effective, the neutralization … must be guaranteed by the big powers, including Communist China … it is time that the countries in South-East Asia signed non-aggression treaties with each other. [...]
In a speech in July 1971 Prime Minister Razak argued that the involvement of major powers was the essential reason Southeast Asia had not been at peace for twenty years. Peace and security could be safeguarded only by “a policy of neutralisation which will ensure that this region will no longer be a theatre of conflict for the competing interests of the major powers”.
It should also be said here that other ZOPFAN signatories like Singapore actually welcomed the AUKUS announcement.
Others (e.g. the NZ peace group I quoted from previously) have more explicitly raised the possibility that Australia or its neighbors might be a step closer to nuclear weapons this way:
“Although Australia is not interested in using HEU to make a nuclear bomb, providing Australia, a state member of the Nuclear Non-Proliferation Treaty (NPT), with HEU (at around the 50% enrichment level) for nuclear-powered submarines, could open the floodgates to other countries acquiring HEU powered submarines in order to develop a capacity to then make a bomb. [...]
