One idea would be to identify which sub function have changed and to check if this changes are mentioned in the Changes file, i.e. by checking if the sub names are mentioned.

I think the GNU diff can show the names of changed function for C code. Maybe there is a way to do similar thing for Perl code.

PS: This remains me on the Pod::Coverage package which checks if there is documentation for every sub function.