Thank you Raphael for this very interesting and challenging problem! The following is an approximate argument supporting both Conjecture 1 and Conjecture 2. Perhaps it can give a hint at how to construct a more rigorous proof.
Let me start by reformulating Conjecture 1 somewhat. As has already been indicated in the question, we can from the $2n$-dimensional vector $v$ construct a $m \times n$ Toeplitz matrix $M$ with elements $M_{m+1-i,j} = v_{i+j-1}$ for $j=1,...n$ and $i=1,...,m$ (where $m=\lfloor \frac n{\log_2n} \rfloor < n$). Defining, furthermore, $a_i = A_{m+1-i}$ (i.e., just reversing the order of the elements), we then have in matrix notation $a=Mw$, and Conjecture 1 can be re-stated in the following form:
Conjecture 1*
For sufficiently large $n$, there exists a Toeplitz matrix $M \in \{0,1\}^{m \times n}$, with $m=\lfloor \frac n{\log_2n} \rfloor$, such that $P(Mw=0)\leq2^{-\frac n4}$.
I will now construct an argument supporting Conjecture 1* (or actually, as we will see, a somewhat stronger conjecture).
Let us define the characteristic function (= "Fourier transform") of the distribution of the vector $a=Mw$ as
$$
\tilde P(\xi) = \left\langle {\rm e}^{2\pi{\rm i}\,\xi^{\rm T}Mw} \right\rangle_w \ ,
\hspace{2cm} (1)
$$
where $\left\langle \cdots \right\rangle_w$ denotes the average over $w \in \{-1,0,1\}^n$ with the probabilities specified in the question. Since the random vector $a=Mw$ has integer components, the quantity we are interested in can be expressed by the following $m$-dimensional integral:
$$
P(Mw=0) = \int_{[-\frac12,\frac12]^m} {\rm d}^m\xi \ \tilde P(\xi) \ .
\hspace{2cm} (2)
$$
On the other hand, the $w$ average in $(1)$ can easily be carried out explicitly, with the result
$$
\tilde P(\xi) = \prod_{j=1}^n \cos^2 \left( \pi \sum_{i=1}^m \xi_i M_{ij} \right) \ .
\hspace{2cm} (3)
$$
We thus have an $n$-fold product of periodic $\cos^2$ terms, being a function of $m$ real variables $\xi_i$, each of which is integrated over the interval $[-\frac12,\frac12]$. Since this multiple integral seems too hard to do, I use the following approximation:
$$
\cos^2 (\pi t) \approx \sum_{k=-\infty}^\infty {\rm e}^{-4\pi(t-k)^2} \ ,
\hspace{2cm} (4)
$$
which has been chosen in such a way that its maximum value is close to $1$ (the maximum of $\cos^2$) and that it also preserves the integral value $\int_{-1/2}^{1/2} {\rm d}t\ \cos^2 (\pi t) = \frac12$ over one period. Now we can re-write $(2)$ as
\begin{align}
P &\approx
\int_{[-\frac12,\frac12]^m} {\rm d}^m\xi \
\prod_{j=1}^n \left[ \sum_{k_j=-\infty}^\infty {\rm e}^{-4\pi \big( \sum_{i=1}^m \xi_i M_{ij} - k_j \big)^2} \right] \nonumber\\
&= \sum_{k\, \in\, \mathbb Z^n}
\left[ \int_{[-\frac12,\frac12]^m} {\rm d}^m\xi \ \
{\rm e}^{-4\pi (M^{\rm T}\xi-k)^{\rm T}(M^{\rm T}\xi-k)} \right] \ . \nonumber
\hspace{2cm} (5)
\end{align}
The integrand is now a multidimensional gaussian, which would be easy to handle if the $k$ sum were an integral instead of a sum, and/or if the bounds of the $\xi$ integration were at infinity instead of $\pm1$. I will now describe ways to circumvent these problems.
First I will try to turn the $\xi$ integration with finite integration bounds into a pure gaussian integral with bounds at infinity. The idea is to perform a singular-value decomposition of $M$, re-interpret $\xi \in [-\frac12,\frac12]^m$ as a random vector with i.i.d. components (each having mean $0$ and variance $\langle \xi_i^2 \rangle = \frac\gamma{8\pi}$), and then apply the central limit theorem. The variance parameter $\gamma$ has the definite value
$$
\gamma\, = 8\pi \int_{-\frac12}^{\frac12}{\rm d}\xi\, \xi^2 = \frac{2\pi}3 \ ,
\hspace{2cm} (6)
$$
but for the moment I will keep it as a parameter. Expressing the $m$-dimensional $\xi$ integration as a stochastic average, $\langle \cdots \rangle_\xi = \int_{[-\frac12,\frac12]^m} {\rm d}^m\xi(\cdots)$, Eq. $(5)$ reads
$$
P \approx \sum_{k\, \in\, \mathbb Z^n}
\left\langle {\rm e}^{-4\pi \big(M^{\rm T}\xi-k\big)^{\rm T}\big(M^{\rm T}\xi-k\big)} \right\rangle_\xi \ .
\hspace{2cm} (7)
$$
Now we use the singular value decomposition $M=V \Sigma U^{\rm T}$ with orthoganal matrices $V$, $U$ and a rectangular diagonal matrix $\Sigma$, containing on its diagonal the (non-negative) singular values $\sigma_i$ of $M$. Denoting the orthonormal column vectors of $U$ by $U_j$ ($j=1,...,n$) and those of $V$ by $V_i$ ($i=1,...,m$) we can write this decomposition as follows:
$$
M = \sum_{i=1}^m \sigma_i V_i U_i^{\rm T} \ .
\hspace{2cm} (8)
$$
The eigenvalues of $MM^{\rm T}$ are $\lambda_i = \sigma_i^2$ ($i=1,...,m$) .
Inserting $(8)$ into $(7)$ then yields
$$
P \approx \sum_{k\, \in\, \mathbb Z^n}
\left\langle {\rm e}^{-4\pi \big( \sum_{i=1}^m \lambda_i \eta_i^2 - 2 \sum_{i=1}^m \eta_i \sigma_i U_i^{\rm T}k + k^{\rm T} k \big)} \right\rangle_\eta \ ,
\hspace{2cm} (9)
$$
with $\eta_i = V_i^{\rm T}\xi$ (i.e., $\eta = V^{\rm T}\xi$). If we assume that all the components of the matrix $V$ have "similar size" ($\approx m^{-\frac12}$) in some suitable sense (for instance, they might be normal distributed with variance $m^{-1}$), it follows from the central limit theorem that for large $m$ the $\eta_i$ are uncorrelated gaussian random variables with zero mean and covariance matrix $\langle \eta_i \eta_j \rangle = \frac\gamma{8\pi} V_i^{\rm T}V_j = \frac\gamma{8\pi} \delta_{ij}$. This in turn suggests that, asymptotically, $(9)$ can be re-written as
\begin{align}
P
&\sim \sum_{k\, \in\, \mathbb Z^n}
\left[ (\gamma/4)^{-\frac m2} \int_{\mathbb R^m} {\rm d}^m\eta \ \
{\rm e}^{-4\pi \big( \sum_{i=1}^m\eta_i^2/\gamma + \sum_{i=1}^m \lambda_i \eta_i^2 - 2 \sum_{i=1}^m \eta_i \sigma_i U_i^{\rm T}k + k^{\rm T} k \big)} \right] \nonumber\\
&\sim \left[ \prod_{i=1}^m \big( 1 + \gamma\, \lambda_i \big)^{-\frac12} \right]
\sum_{k\, \in\, \mathbb Z^n}
\exp {-4\pi \left[ \sum_{i=1}^m \frac{(U_i^{\rm T}k)^2}{1 + \gamma\, \lambda_i} + \sum_{j=m+1}^n (U_j^{\rm T}k)^2 \right]} \ . \nonumber
\hspace{.5cm} (10)
\end{align}
Note that according to $(10)$, it seems that the quantity $P$ asymptotically only depends on the eigenvalue spectra of the (symmetric) matrices $\Lambda = MM^{\rm T}$, i.e. on the $\lambda_i$. (In addition, it may depend, in some subtle way, on the orthonormal vectors $U_j$ defined by the singular value decomposition of $M$, but let me disregard this possibility for the moment.)
The matrix elements of $\Lambda = MM^{\rm T}$ can be expressed in the form
$$
\Lambda_{ij} = \frac n4 (\delta_{ij} + 1) + \mu_{ij} \ ,
\hspace{2cm} (11)
$$
where $\mu_{ij}$ are gaussian random variables with mean $0$ and variance $\langle \mu_{ij}^2 \rangle \approx \frac n4$ (but not necessarily uncorrelated with each other).
Using random matrix theory one can shown that the distribution of the eigenvalues $\lambda_i$ of such a $m \times m$ matrix $\Lambda$ for $m \ll n$ is sharply peaked around $\lambda = \frac n4$ (the width of the distribution being $\lambda_{\rm max} - \lambda_{\rm min} \approx \sqrt{mn}$), apart from a single large eigenvalue which is of the order $\lambda \approx \frac{mn}4$. Strictly speaking, random matrix theory guarantees this only if either the $\mu_{ij}$ or the original matrix elements $M_{ij}$ are independent random variables, but numerical experiments suggest that it also holds for random Toeplitz (or circulant) matrices $M$ (I have done such tests for matrix sizes up to $m=4\times10^3$, $n=2\times10^5$).
From this I conclude that we can replace all $\lambda_i$ in $(10)$ by $\frac n4$, except one which is $\sim \frac{mn}4$.
Now we can try to further evaluate $(10)$. If we were allowed to replace the $k$ sum by an $n$-dimensional integral then we would obtain
\begin{align}
\sum_{k\, \in\, \mathbb Z^n} \exp-4\pi(\cdots)
&\sim \int_{k\, \in\, \mathbb R^n} {\rm d}^n k \ \exp-4\pi(\cdots) \nonumber\\
&= 2^{-n} \left[ \prod_{i=1}^m \big( 1 + \gamma\, \lambda_i \big)^{\frac12} \right] \nonumber\\
&\sim 2^{-n}\, m^\frac12 \left( \frac{\gamma\, n}4 \right)^{\frac m2} \ , \nonumber
\hspace{2cm} (12)
\end{align}
which together with $(10)$ would immediately imply that $P$ has the lowest possible value $P \sim 2^{-n}$ for any $m$. However, we know that at least for small $m$ the last expression in $(12)$ must be wrong, since the $k=0$ term of the sum is always equal to $1$ and so that the whole sum can never become smaller than $1$. Furthermore, $(12)$ can of course only be a reasonable approximation if many terms in the sum make some substantial contribution, i.e., if the sum itself is much larger than $1$.
On the basis of the above arguments I therefore believe that the following holds, asymtotically for large $n$:
$$
\sum_{k\, \in\, \mathbb Z^n} \exp-4\pi(\cdots) \sim \max\left\{ 1,\ 2^{-n}\, m^\frac12 \left( \frac{\gamma\, n}4 \right)^{\frac m2} \right\} \ .
\hspace{2cm} (13)
$$
We can now combine $(13)$ with $(10)$. Asymptotically, the factor $m^\frac12$ in $(13)$ is irrelevant and $2^{-n}\, m^\frac12 \left( \frac{\gamma\, n}4 \right)^{\frac m2} \geq 1$ is equivalent to $m \geq \frac{2n}{\log_2 ( \gamma n/4)}$, and so we obtain:
$$
P \sim
\begin{cases}
\quad 2^{-n} \ , \quad m > \frac{2n}{\log_2 ( \gamma n/4)} \\
\left( \frac{\gamma\, n}4 \right)^{-\frac m2} \ , \quad m \leq \frac{2n}{\log_2 ( \gamma n/4)}
\end{cases} \ .
\hspace{2cm} (14)
$$
In particular, if we choose $m$ to be
$$
m = \beta \frac{2n}{\log_2 ( \gamma\, n/4)} \ ,
\hspace{2cm} (15)
$$
with some constant $\beta \in ]0,1]$ of our choice, then we obtain
$$
P \sim \left( \frac{\gamma\, n}4 \right)^{-\beta \frac{n}{\log_2 ( \gamma n/4)}}
= 2^{-\beta n} \ .
\hspace{2cm} (16)
$$
Furthermore, $(15)$ implies that $m \sim \beta \frac{2n}{\log_2 n}$ asymptotically, so the assumptions in Conjecture 1* (or in the original Conjecture 1) correspond to $\beta=\frac12$. In that case, $(16)$ seems to lead to the prediction $P(Mw=0) \sim 2^{-\frac n2}$, for any "typical" random matrix $M \in \{0,1\}^{m \times n}$, whether of a Toeplitz form or not. This is a stronger statement (exponent larger by a factor 2) than Conjecture 1.
Finally, as already indicated in the beginning of this answer, I believe that the presented argument also has a bearing on Conjecture 2. Namely, from the first line of $(14)$ (or by setting $\beta = 1$ in $(15)$ and $(16)$) we see that it predicts that if $m \geq \frac{2n}{\log_2 n}$ then $P(Mw=0) \sim 2^{-n}$ asymptotically. As far as I understand, this in turn would mean that the set of columns of a randomly chosen matrix $M \in \{0,1\}^{m \times n}$, whether of a Toeplitz form or not, is "weakly dissociated" in the sense that the fraction of all sub-sets whose sum is not distinct from all others tends to zero in the limit $n \to \infty$.