Does the protective layer of Aluminum oxide form on the surface of aluminium alloys (such as Al-Zr) as well?
Short answer: Yes.

Long answer: Any alloy containing 'passivating' elements such as aluminum, which have the tendency to form a protective oxide as you describe, has the potential to also form the same sort of passivating oxide layer as the pure material.  It's not guaranteed, though.

Pure zirconium also forms a passivating oxide $(\ce{ZrO2})$$^{(1)}$, so the AlZr alloy you mention is almost certain to form a similar protective oxide.

More broadly, a major area of research at present is in the 'alumina-forming' alloys ("alumina" is another word for aluminum oxide, $\ce{Al2O3}$), where aluminum is included in, e.g., steels or nickel superalloys, to try to achieve this passive aluminum oxide layer on the surface in high-temperature, corrosive environments$^{(2-5)}$.  With materials like a stainless steel-plus-aluminum, the passive oxide scale only forms if the alloy has the right percent range of aluminum -- otherwise, the aluminum oxide ends up staying spread throughout the metal and not concentrating at the surface.  If the alumina doesn't end up spread evenly over the surface, you don't get nearly as good of a protective effect.

(1) http://www.mtialbany.com/metals/zirconium/
  (2) http://topaz.ethz.ch/function/web-het-secured/pdfs/Prescott-92.pdf
  (3) http://www.metalle.uni-bayreuth.de/de/download/publications_downloads/Bensch__Sato__Warnken__Affeldt_______Reed__Glatzel__Acta_Mat_.pdf
  (4) http://www.netl.doe.gov/File%20Library/Events/2010/ods/Gordon_Tatlock_Corrosion.pdf
  (5) http://www.ornl.gov/science-discovery/advanced-materials/science-to-energy-solutions/alumina-forming-austenitic-alloys-licensed