minimize $l_1$ distance between vectors
Define $r_i=a_i/b_i$.  Sort the vectors in increasing order of $r_i$.  Let's assume (wlog) the $r_i$'s are in increasing order, i.e., $r_1 \le r_2 \le r_3 \le \cdots$.  Let $R=\{r_1,r_2,\dots,r_n\}$.

Notice that your objective function is differentiable at all $x$ such that $x \notin R$.  In fact, it is linear on each open interval $(r_i,r_{i+1})$.  It follows that it attains a maximum at one of the values $r_i$.

So, it suffices to try each of $r_1,r_2,\dots,r_n$ as possible values for $k$, and see which minimizes the objective function.  This leads to a simple $O(n^2)$ time algorithm.  With some optimization and clever tricks you can get this down to $O(n \lg n)$ time, by avoiding re-computing the objective function from scratch each time and re-using work.