I started noticing the same thing in my own code and specifically wrote an object class to let me centralize the management of error and similar messages, including ones containing run-time content, like this:
  print $error_messages->file_open_failed($input_file);

You don't actually have to define a file_open_failed object method; that's syntactic sugar that AUTOLOAD turns into the conceptual equivalent of print $error_messages->construct_message('file_open_failed', 'myfile');.

In my case the issue wasn't I18N as much as wanting to have consistent messages across a sprawling code base, and keep them in a single place for easier documentation -- but the basic issue is not dissimilar.

I've made the module available here; sorry for the off-site link, but I haven't yet gotten around to CPANning it. Feedback is welcomed!

As for things like the name of a program, I sometimes consider that a candidate for use constant..., though unfortunately that doesn't help if you need to change the name in documentation and other collateral. Even macro expansion or search-and-replace isn't perfect, because if you're not careful your documentation may contain phrases like "a FooBar report may contain Bazzes", which after transforming, say, {FooBar => AlphaBar and Baz => Blarg} can become something rather convoluted like "a AlphaBar report may contain Blargzes".