The obvious answer here is that experience is the only thing that matter. Reverse engineer tons of stuff. Expand your knowledge. Share what you've learned. Etc etc.
But of course, getting a certification won't do you any harm and as far as I am concerned, will only count as a plus on your CV.
However; having a certification on your CV doesn't get you a job on it's own. In today's day and age the recruiters are actively searching for people who "do more". I would suggest that you start building your "brand". Make yourself visible in the community. Discuss new malware on Twitter. Share your knowledge here on security.SE etc. That's what ultimately is going to secure your position as a malware analyst.
When it comes to what certs to take; I've heard and read a lot of good things about the GIAC Reverse Engineering Malware (GREM) certification.
I've also been looking at a lot of open Malware Analyst positions, and here are some of the varous certifications they ask for. There are probably many more, and these are usually just suggestions from the hiring-side. Don't be afraid if your certification isn't on their "we want someone with these certs"-list, they might just not have concidered (or hear of) the one you have (which isn't necessarily a bad thing, HR is HR after all).
For your last question; Take a certification when you have the money, time and done enough research on the certification to make you certain that it covers exactly what you want to learn. There is no rush, and some employers even pay for certifications once your hired. So my best suggestion is, start building your brand and grow your knownledge.