The square can be a primitive cell for a Bravais lattice. It fulfills both requirements:
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.
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)