In British English (and I believe AmEng too) there are idiomatic ways of stating specific times on the clock, although these expressions do not necessarily apply when speaking about hours and minutes in general.
You can write any time numerically in 12, or 24-hour format:
Trains depart at 15:16, 15:46. 16:16 etc
How we say those times depends on the number of minutes past the hour, and if writing them in words, we would write them as they should be spoken.
We don't usually use the words "hours" and "minutes" when quoting a specific time, and when the minutes are divisible by 5, for example:
- Five past four (16:05)
- Twenty-five past five (17:25)
- Twenty to six (17:40)
Also, when the time is precisely 15, 30, or 45 minutes past the hour, we tend to say:
- A quarter past five. (17:15)
- Half-past five (17:30)
- A quarter to six (17:45)
However, when the number of minutes is not divisible by 5, we do include the word "minutes", for example:
Six minutes past four (16:06)
In everyday situations, British English speakers tend to round times like this and say things like "It's nearly ten past four", or "It's just gone five past four". Obviously that would not be the case with a transport timetable.
For the reasons above, we would definitely include the word "minutes" in your example, if only because it is an "unrounded" number of minutes (not divisible by 5):
The train departs at 16 minutes past every hour.
OR
The train departs at 16 minutes past each hour.
It is also idiomatic, when speaking about any hour, to say "past the hour", as in this example from MW dictionary:
Trains leave every hour at ten minutes past the hour.