Non-Orthogonal Vectors Problem
When $k$ is given as part of the input, the second problem is equivalent to the monochromatic Max-IP problem (given $S \subseteq \{0,1\}^d$, find $\max_{(a,b) \in S, a\ne b} a \cdot b$). 

Recently I and Ryan Williams have an (unpublic yet) work showing that when $d = O(\log n)$, OVP and a bichromatic version of Max-IP (given $A,B$, find $\max_{(a,b) \in A \times B} a \cdot b$), is actually equivalent: that is, if one of them has $n^{2-\varepsilon}$ time algorithm, so does the other one. (The reduction from OVP to Max-IP is well-known, the new reduction here is that from Max-IP to OVP).

Since the monochromatic version of Max-IP can be reduced to the bichromatic version, the above result also implies that when $d = O(\log n)$, monochromatic Max-IP can be reduced to OVP.

I believe it is an open question that whether OVP can be reduced to monochromatic Max-IP. This is also closely related to establishing the OV-hardness for the closest pair problem (see e.g. On the Complexity of Closest Pair via Polar-Pair of Point-Sets)

For monochromatic Max-IP, there is an algorithm with running time $n^{2 - 1/\widetilde{O}((d/\log n)^{1/3})}$ time algorithm by Alman, Chan and Williams (also pointed out by Rasmus), for which I believe is the state of the art. While the best algorithm for OVP runs in $n^{2 - 1/O(\log c)}$ time when $d = c \log n$, which is significantly faster.

Also, the approximate version of Max-IP is also studied by this paper On The Hardness of Approximate and Exact (Bichromatic) Maximum Inner Product, which gives a characterization for the bichromatic case (that is, for which dimensions $d$ and approximate ratio $t$, the problem can be solved in $n^{2-\varepsilon}$ time?). The algorithm in that paper also works for the monochromatic case.