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 code, i use (updateable-by-script) boilerplates:
use mro 'c3';
use English qw(-no_match_vars);
our $VERSION = 2.3;
use Fatal qw( close );