Clearly the Knight cannot be a Construct in the strict rules sense of the word. For you CANNOT be a 4th level fighter AND be a Construct - they are incompatable by definition.
I'd say the Knight is a Magical Construct in a more generic sense of the word.
He would not:
be "immune to mind-influencing effects and to poison, sleep, paralysis, stunning, disease, death effects, and necromantic effects,"
be "repaired in the same way an object can,"
immune "to critical hits, subdual damage, ability damage, ability drain, or energy drain,"
"have darkvision with a range of 60 feet" (unless a dwarf, I suppose),
have an attack bonus as a cleric,
etc.
Keep it simple. He is a 4th level fighter with skills and feats, but no history. He knows how to fight and is loyal, but knows little else beyond very general knowledge - like literacy in the local language. he should have no knowledge of any locations, politics, etc.
It is a good thing he knows his purpose, or he'd be pretty messed up. Treat him like someone with amnesia, and I think you've got the right idea.