Would "canarului" work instead of "canarul lui"?
No. Canarului means canary's. Canarul lui means his canary.
why is "caut pe canarul său" wrong?
Why there's nothing used for "for"?
that was my question too, but answers are sparse nowadays. I guess it is only used in the accusative constructions like: (eu) îl caut pe canarul lui but I might be wrong :-)