I'll give a partial answer to your Question #2. If you know $k$ and also how many entries are equal to $1$ in each column, you can actually compute the absolute value of the determinant exactly.
By the answer you linked to, we know that
$$
A^TA = \begin{bmatrix}v_1 & k & \cdots & k \\ k & v_2 & \cdots & k \\ \vdots & \vdots & \ddots & \vdots \\ k & k & \cdots & v_n \end{bmatrix},
$$
where $v_j$ is the number of ones in the $j$-th column of $A$. In particular, $k \leq v_j \leq n$ for all $j$. So we can write
$$
A^TA = k\mathbf{1}\mathbf{1}^T + D,
$$
where $\mathbf{1}$ is the all-ones vector and $D$ is a diagonal matrix whose diagonal entries are $v_j-k$, which are are between $0$ and $n-k$ (inclusive).
By the matrix determinant lemma, we can compute
\begin{align*}
\det(A)^2 = \det(A^TA) & = \det(k\mathbf{1}\mathbf{1}^T + D) \\
& = (1 + \mathbf{1}^T D^{-1}\mathbf{1})\det(D) \\
& = \left(1 + \sum_{j=1}^n \frac{1}{v_j-k}\right)\left(\prod_{j=1}^n (v_j-k)\right),
\end{align*}
as long as $D$ is invertible. The only way that $D$ can fail to be invertible, assuming $A$ is invertible, is if there is a single index $j$ for which $v_j = k$ (this is explained in the same answer linked before). WLOG I will assume that this special index is $j = 1$. By a continuity argument, in this case we have
$$
\det(A)^2 = \prod_{j=2}^n (v_j-k).
$$
Putting all of this together gives the following explicit formula for $|\det(A)|$ (again, assuming that if any $v_j = k$ occurs, it occurs when $j = 1$):
\begin{align*}
|\det(A)| = \begin{cases}
\sqrt{\prod_{j=2}^n (v_j-k)}, & \text{if $v_1 = k$} \\
\sqrt{\left(1 + \sum_{j=1}^n \frac{1}{v_j-k}\right)\left(\prod_{j=1}^n (v_j-k)\right)}, & \text{otherwise}.
\end{cases}
\end{align*}
You can use this to get bounds or whatever is most well-suited to your purposes. For example, if you don't know exactly what the $v_j$'s are, you can use the fact that $0 \leq v_j-k \leq n-k$ to derive the bound
$$
|\det(A)| \leq \sqrt{n+1}(n-k)^{n/2}.
$$
