Is it true that every bounded sequence $\phi: \mathbb{Z} \rightarrow \mathbb{C}$ is the image of some Borel measure $\mu$ under the Fourier transform $\mathcal{F}$, i.e. $$ \forall\, k \in \mathbb{Z}, \, \phi(k) = \int_{(-1, 1]} e^{- 2 \pi i k \cdot \omega} d\mu(\omega) \, \, ? $$ If not, what would be a counterexample?
If $\phi \in l^{\infty}(\mathbb{Z})$ is positive definite, then the answer is yes and the Fourier preimage $\mu$ is a positive measure by Bochner's Theorem.
Writing a Borel measure $\mu$ as a linear combination of positive measures, the question is then equivalent to asking whether the positive definite functions span $l^{\infty}(\mathbb{Z})$.
In turn, this is the same as asking whether a bi-infinite Toeplitz matrix $$ M = [M_{ij}]_{i, j \in \mathbb{Z}} \,\, ( = \phi(i-j) ) $$ is in general a linear combination of (formally) positive semidefinite bi-infinite Toeplitz matrices.
(The matrix formulation seems to suggest the answer is "no". The positive and negative parts of an $n \times n$ symmetric Toeplitz matrix need not be Toepiliz.)
No, it's not true that every bounded sequence is the image of a Borel measure under the Fourier transform.
One counterexample is the following: $$\phi(k) = \text{p.v.} \int_{-1/2}^{1/2} \frac{e^{-2 \pi i k x}}{x} \, dx.$$
In other words, this sequence is the Fourier transform of the periodic distribution $F$ given by $$\langle F, \psi \rangle = \text{p.v.} \int_{-1/2}^{1/2} \frac{\psi(x)}{x} \, dx$$.
There are now two points to sort out.
(1) The sequence $\phi$ so defined is bounded.
To see this, first note that the real part is identically zero, since the real part of each integrand is an odd function.
The imaginary part of $\phi(k)$ can be written as $$-2 \int_{0}^{1/2} \frac{\sin(2 \pi k x)}{x} \, dx = -2 \int_{0}^{k/2} \frac{\sin(2 \pi y)}{y} \, dy,$$ and using integration by parts you can show that this remains bounded as $|k| \to \infty$.
(2) This sequence does not arise from a Borel measure.
The distribution $F$ pretty clearly doesn't come from a (finite) Borel measure because of the positive and negative divergences at 0. Of course it's like the difference between two non-finite positive measures, but I imagine that's outside the bounds of what you were going for.
One could also justify why there isn't a finite Borel measure whose Fourier transform coincides with that of $F$. I'd view this as a general property of distributions and the Fourier transform, i.e. the Fourier transform is 1-to-1. As a reference, for periodic distributions this is briefly touched on in Folland's Real Analysis at the top of p. 298.