The Sydney Gazette and New South Wales Advertiser, Advertising March 16 1806, page 3. Retrieved 20 April 2016, nla.news-page6218
The first restaurant in Australia was attached to a hotel called the Freemasons' Arms. It was the first licensed hotel in New South Wales, run by James Larra, who was transported for stealing a silver tankard from a coffee-house in King's Cross, London.
He settled in Parramatta in 1796 and built a wattle and daub hut at first, later rebuilding in brick in 1800 and employing a French chef (from One continuous picnic p 112).
You can read early Australian newspaper articles mentioning the Freemason's Arms through Trove's digitised newspapers.
It seems likely that the first Asian restaurant would have opened on one of the gold fields. Here is a picture of a possible contender, John Alloo's Chinese restaurant in Ballarat, 1853.
Newspaper articles about John Alloo's Chinese restaurant are also available through Trove's digitised newspapers.