The square can be a primitive cell for a Bravais lattice. It fulfills both requirements:

1. any point of the lattice can be reached by the linear combination $\mathbf P = n_1\mathbf a + n_2\mathbf b$, where $\mathbf a$ and $\mathbf b$ are the primitive vectors (in this case the orthogonal vectors from a given point to its nearest neighbours at right and above), and $n_1$ and $n_2$ are integers. So, it is a Bravais lattice.

2. The area defined by $\mathbf a$ and $\mathbf b$ is the minimum to replicate and cover all the space. So, it is a primitive cell.

The hexagon can be replicated to cover all the space, fulfilling (2). But it is not possible to choose 2 vectors $\mathbf a$ and $\mathbf b$ so that $\mathbf P = n_1\mathbf a + n_2\mathbf b$ for any $\mathbf P$ of the lattice. So it doesn't define a Bravais lattice as required by the question.

However, we can define a Bravais lattice, taking the horizontal midpoint of each 2 points of the hexagonal lattice as the actual lattice point. The lattice formed by those midpoints have a Wigner-Seitz primitive cell with the shape and size of the hexagon! (See here)

So if we have atoms following an 2-D hexagon lattice, their sites don't form a Bravais lattice. That is formed by another lattice, taking pairs of them as the lattice points.

The square can be a primitive cell for a Bravais lattice. It fulfills both requirements:

1. any point of the lattice can be reached by the linear combination $\mathbf P = n_1\mathbf a + n_2\mathbf b$, where $\mathbf a$ and $\mathbf b$ are the primitive vectors (in this case the orthogonal vectors from a given point to its nearest neighbours at right and above), and $n_1$ and $n_2$ are integers. So, it is a Bravais lattice.

2. The area defined by $\mathbf a$ and $\mathbf b$ is the minimum to replicate and cover all the space. So, it is a primitive cell.

The hexagon can be replicated to cover all the space, fulfilling (2). But it is not possible to choose 2 vectors $\mathbf a$ and $\mathbf b$ so that $\mathbf P = n_1\mathbf a + n_2\mathbf b$ for any $\mathbf P$ of the lattice. So apparently it is not a Bravais lattice as required by the question.

However, if we define a lattice as the right picture of the Agnius answer, it is easy to verify that the condition (1) is now fulfilled. And we can define a primitive cell called Wigner-Seitz. It is the shape resulting from the following procedure: choose any point, draw straight lines to all nearest neighbours, cut these lines at the middle, join that cutting lines.

That primitive cell is indeed an hexagon, and there is an hexagon for each point, covering all the space. So both conditions are also fulfilled. (See here)