Checking for the existence of the Changes file is available in Test::Kwalitee via the have_changelog test. I'm not too sure about the check for format though.