When followed by an adjective or a noun (with no article) faire can indeed be synonym of avoir l'air/paraître.
This particular meaning derives from one of the numerous meanings of faire. The Dictionnaire culturel en langue française lists six semantic groups for the meaning of faire:
I. Réaliser (qqch. ou qqn), agir de manière à faire exister. (construire, fabriquer une maison - to build a house)
II. Effectuer. (une opération, un travail - to perform)
III. Déterminer dans sa manière d'être. (to make)
IV. Être la cause de. (faire tomber - to drop, faire avancer - to move forward)
V. Exprimer les contions de l'atmosphère. (Il fait beau - the weather's fine)
VI. Emploi comme substitut d'un autre verbe (this use is outdated). (Je ne parle pas comme il le fait (nowadays it's more usual to repeat the verb in such a sentence: je ne parle pas comme il parle - I don't speak as he does)
N° III, the meaning we are interested in here, appeared at the end of the 10th century. In the Dictionnaire culturel en langue française we can follow the semantic evolution thus:
- Arranger, mettre dans un état convenable. (Faire son lit)
↓
- Former, instruire. (Cette école fait de bons traducteurs)
↓
- Donner une qualité. (Il a été fait général)
↓
- Changer, transformer. (Ils en ont fait un bon petit soldat)
↓
- Représenter, agir comme. (Isabelle Adajni a fait Marguerite Gautier dans « La dame aux camélias », faire l'idiot)
↓
- Avoir l'air de, donner l'impression.
Although faire can only be synonym of avoir l'air if followed by an adjective or a noun (without an article), we would not always use faire in all cases where it is followed by an adjective or a noun. For example I would never use it to say :
Ce gâteau a l'air cuit. (that cake looks cooked).
Elle a l'air prête. (It looks as if she's ready).
The only reason for that I can find so far is that we will not use faire if a transformation is involved, but only when referring to the innate quality of something or someone. It's only an assumption though, because I can find no better explanation at the moment.
Personally I would not always interchange faire and avoir l'air even when possible. There's a feeling, maybe not of informality but of triteness about faire, and I would tend to avoid using it whenever I can.