Why does Postgres tell me "no pg_hba.conf entry for host..." when I have already modified this file?

Per documentation, the meaning of samerole in the database column is:

The value samerole specifies that the requested user must be a member of the role with the same name as the requested database.

The error message indicates that the rejected connection is attempted with user "postgis_user", database "postgis_prototype". Since the user name and database name differ, the rule with samerole cannot match (well, unless there is a postgis_prototype role with postgis_user as a member, but if you had set that up, surely you would have mentioned it in the question).

The simplest solution is probably to list the authorized databases in the 2nd column, the authorized users in the 3rd column, and forget about using samerole.

You may use comma-separated list in these columns, or split them into several rules.

The rules in pg_hba.conf are evaluated from top to bottom, stopping at the first matching rule.

The solution of accepting everything with host all all 0.0.0.0/0 md5 is indeed not recommended at all if your server can be reached from the Internet. There are evil bots out there that try to connect as the postgres superuser to every reachable Postgres installation.