I am trying to understand why the second paragraph under the stated division algorithm seems to mention the verification of one of the values for $q_i$ takes $O(l)$ time, while I think it would take $O(k)$ (checking $q_i$ in one of the inequalities that define the floor function seems to take $O(k)$ time, taking into consideration that before this algorithm we are given addition and subtraction algorithms in $O(\max(k,l)$) time and an algorithm for multiplication in $O(kl)$ time, for two integers of $k$ and $l$ digits, respectively).
Source: page 58 of Victor Shoup's free book "A computational introduction to number theory and algebra".
means to construct the table $$ 0\cdot B^i b, 1 \cdot B^i b, \dots, (B-1) \cdot B^i b \text{,} $$ by repeated addition, requiring $O(B-1)$ additions of size either $\ell+1$ or $\ell+i+1$. (The "$+1$" is to manage the carries into the $B^\ell$ digit of the accumulation. We only include the "$+i$" if we must explicitly include the trailing $i$ zeroes in the addition instead of producing them directly afterwards -- that is we already know every item on that list has (at least) $i$ trailing zeroes, so we need send them to the adder, we can just extend the adder's result by these zeroes.) For this list, $i$ and $1$ are constant, so $O((B-1)\ell)$ bit operations.
Either after constructing this list, or as we construct this least, we want to know the last member of this list that is less than or equal to $r$. This only requires comparing the $\ell+1$ (leading) bits of the table entry (because the trailing zeroes cannot compare greater than whatever bits are in the tail of $r$). This is also $O((B-1)\ell)$.
Taken together $O(2(B-1)\ell) = O(B\ell)$ or, as the source observes, since $B$ is constant, $O(\ell)$.
It's baffling that you think $k$ is relevant. The variable $a$ appears nowhere in "$q_i = \lfloor r/(B^i b) \rfloor$".