Australia has very strict laws on weapons, replica weapons and licencing. Different states also have various levels of laws and restrictions. There are also guidelines and licences required for importing, owning and safely storing weapons as well as imitation weapons. Even more, different TYPES of replicas (ie: pistol vs rifle, archaic vs modern etc) have different requirements. I would assume exporting these items has similar restrictions. For some states and certain classes of weapons, the law doesn't even really distinguish between a working weapon and a replica - they are all considered restricted items that require a licence to own, use, import and export.
As for the reason they quoted: "if a 'reasonable' person 'could' mistake it for an actual weapon, then it is a weapon." I'm pretty sure that's not just a DHL agent's petty thing, that's close to the actual wording in the firearms legislation itself. Essentially, if it's a close enough replica that a random bystander might think its real, then it is treated with a MUCH higher level of restriction and licence requirement. There's been enough incidents over the years, of people being shot while carrying toys, or people using replicas or toys to commit crimes, that Australia has decided to impose stricter laws (depending on the state of course - NSW where I live is especially strict, while QLD and SA have much looser laws)
The NERF Pulse rifle isn't a restricted replica firearm because of the colours, but as soon as you paint it up to look like the prop, it passes over that ambiguous line and get's reclassified. I've gone through all of this multiple times over the years because I collect Transformers toys, and owning something like a transforming Megatron figure technically requires a replica firearms license, and it has to be stored in an approved lockable gun-safe, that has been inspected and approved by your local police!!
I've been investigating this all myself recently because I was contemplating importing a Blade Runner replica or trying to get a replica Mauser to build a DL-44 Han Solo blaster. Ultimately I concluded that the compliance requirements were much too onerous and costly, and there was just too much risk of being fined, or simply having costly imports destroyed.
Depending on where you sent it from, what cities/states it passed through on it's way out of the country, and what level of scrutiny it received on the way, it could have triggered any number of redflags. From what I've read, even the mood of the customs agent who caught it on the day can mean the difference between it being returned with a polite letter and the offending item going straight in the furnace.
Don't want to get too political but... while it annoys me no end and it really puts a cramp on some of the props we can collect, when I look at gun violence and crime rates in countries like the US, not having a Megatron toy on my shelf seems a small price to pay. My daughter is 12 and my son is 6 and they are safe at their school every day, without security guards, metal detectors etc. They don't even know what a "duck and cover" drill is, and hopefully will never have to. When I think about that, I guess I'm okay with the law being a little too strict on this one.