A trip to the city will have you covered, there are lots of vegan restaurants and we have a vegan shop I think too. I'll let someone else answer because, although i'm in Melb, i'm not near the city so haven't had the pleasure of a lovely vegan trip yet.
The first things that come to mind though:
Lord of the fries (chips and burgers)
Veggie Bar (veg restaurant with lots of options)
Lovin' hut (asian food)
And there are a few lentily places
I'm not sure what our vegan shops are called, and may have the restaurant names wrong too as it is 2am and i'm suffering from wanting to sleep but my brain not letting me.
If you want a big road trip there's Edgars Mission in kilmore..but I am not sure if they are doing any more events or going to any markets in that time.