As you've already found out, laksa is not a single dish, but a constellation of them -- there's something like a dozen major varieties in Malaysia alone, plus those in Singapore, Indonesia, etc. Wikipedia has a pretty exhaustive rundown. Somewhat oddly, Kuala Lumpur does not have its own variety, which explains why you're not seeing laksa joints around every corner the way you would in eg. Singapore.
Australian laksa is usually closest to laksa lemak, a curry-based laksa with coconut milk (lemak in this case means coconut cream), which is mostly associated with Singapore. Katong laksa, after the Singapore district of Katong, is particularly well-known:
Note the sparse toppings compared to the Aussie style of chucking in anything and everything: a real Katong laksa has only a few slices of fish cake and some raw cockles (shudder) or prawns (my preference!).
The other major style is assam laksa (lit. sour laksa or tamarind laksa), which uses sour tamarind paste instead of coconut milk plus stirs in ground fish. It tastes very different, and is often very spicy, but it's also quite addictive when you get used to it. It's a specialty of Penang.
(courtesy MichaelJLowe / Wikipedia)
And then you've got Sarawak laksa, a crazy blend of the two; Johor laksa made with Italian spaghetti (I kid you not!), Kelantam laksam (not a typo), which has wide fettucini-style rice noodles in a mild coconutty stew instead of a soup, Betawi laksa with bits of intestines floating about (don't worry, you won't find this outside Jakarta), etc etc.
One good place to try these all is the Laksa Shack chain, which has outlets in many of Kuala Lumpur's malls, including the food court at KLCC (below Petronas Towers). Their website is useless, but all they do is laksa in a dozen or so varieties. Compared to Jalan Alor, there's not much in the way of ambience, but the food's pretty cheap and authentic (around RM10 a bowl, IIRC) and air-con comes in handy if you tackle their assam laksa! The Kelantanese sit-down restaurant on the top floor of KLCC also does a pretty mean laksam.