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};
[download]

(The "utf8::" functions are always present. No need to "use" anything.)