Complexity of generating a pseudo-Boolean function
There's a straightforward way to construct a function $f_z:\{0,1\}^n \to \mathbb{R}$ that is zero at only a single point $z=(z_1,\dots,z_n)$ and strictly positive everywhere else: namely,

$$f_z(x_1,\dots,x_n) = (x_1-z_1)^2 + (x_2-z_2)^2 + \dots + (x_n-z_n)^2.$$

Based on this, we can easily construct a function $g : \{0,1\}^n \to \mathbb{R}$ that is zero at only the points $z[1],\dots,z[k]$ and strictly positive elsewhere: namely,

$$g(x) = f_{z[1]}(x) \cdot f_{z[2]}(x) \cdots f_{z[n]}(x).$$

It follows immediately that the pseudo-Boolean function $g$ has global minima at exactly the points $z[1],\dots,z[k]$ and no others, so it meets all your criteria.  This "algorithm" is simple and efficient.