I usually make those the first two non-comment non-blank lines in the file; and I put use strict; first as a matter of aesthetic taste — that both puts them in alphabetical order and gives a nice visual lead towards the right, where the later use statements are likely to end, since most module names are longer than warnings.
You are right: I think of package as part of the file header, so it goes in the very first line in a module, like the #! line in a script. I think that most of my code would probably run under 5.6, so my scripts generally lack use VERSION. I may need to see about changing that. :-)
In my environment, I prefer to specify 'feature' rather than 'version' in part because it is much easier to specify correctly. When a module fails due to compatibility issues, 'feature' helps a maintenance programmer modify the module for an older perl. (If he choses to upgrade perl, he will probably upgrade to the newest version and not care about what is the oldest one he can get away with.) I do understand that 'version' is required by many development tools. That does not apply to me - at least not yet.
In my code, i use (updateable-by-script) boilerplates:
use mro 'c3';
use English qw(-no_match_vars);
our $VERSION = 2.3;
use Fatal qw( close );