カレッジを卒業してすぐであれば Post Graduate Work Permit (でしたっけ?)の申請が可能だから「就職活動中」でも延長できたかも知れませんが、普通に考えたら学生や観光で滞在している人が「仕事を見つけるため」と言って観光ビザが許可されないのは当然ですよ!なんでそんな理由書いたのか、とにかく最悪の理由ですね。
客観的に見ると、今更猫のことを説明して延長申請しても「何故嘘をついたのか」ということになるし、不法就労しようとしているとか疑われても仕方がない状況ですよ。再度の申請はまず無理だと思います。
まず、ビザ却下のお知らせはいつ受け取ったのですか?
また、「XX日までに出国するように」といった内容は書いてありましたか?
期限より前にカナダを出れば問題ないはずです。出国そのものはカナダ側での審査はとくにないのですから、その場で不法滞在でつかまることはないでしょう。11日以降に猫ちゃんを連れてできるだけ早く帰った方がいいと思います。次回カナダに戻ろうとしたときには入国審査が厳しくなる(あるいは入国拒否される)可能性はありますが...。