I assumed I needed "use utf8" as the Š characters are "in the code"
If your source file is UTF-8 encoded, you do. It decodes it.
but if I uncomment "use utf8", none of the translations or substitions have any effect, I just print out the original text each time.
I agree with moritz. That means the database is returning the strings encoded. You need to decode them.
my $p = $sth->fetchrow_hashref;
utf8::decode( $p->{town} );
my $town = $p->{town};
(The "utf8::" functions are always present. No need to "use" anything.)