Update: An idea very similar to this one is described in "Digital Access to Comparison-Based Tree Data Structures and Algorithms".
Here's an idea for a structure that might meet these bounds.
It uses an balanced binary search tree where each node is annotated with a pair of integers in $[-1,k-1]$ to indicate how much of the prefix of the key does not need to be compared again with the search key.
Notation
A shared prefix pair is a pair of integers associated with a key, called the focus, and a set of string keys not containing the focus, called the context.
For a focus $f$ and context $c$, if $\forall y \in c, f < y$, then the left shared prefix (the left value in the shared prefix pair) of $f$ and $c$ is $-1$.
Otherwise, let $g$ be the largest key in $c$ such that $g < f$.
This is called the left neighbor of $f$ in $c$.
Then the left shared prefix $i$ is the largest integer such that $f[i] > g[i]$ and $\forall j < i, f[j] = g[j]$.
The right shared prefix and right neighbor are defined symmetrically.
Search
Annotate each node in a balanced binary search tree with a shared prefix pair, using the key at that node as the focus and they keys of its ancestors in the tree as the context.
I'll first describe how to search for a string key (the needle, as in "needle in a haystack") in an annotated tree, then describe insertion and deletion.
During search, maintain a shared prefix pair with the needle as the focus and the keys of the nodes inspected during the search as the context.
By the definition above, we start with a shared prefix pair of $(-1,-1)$.
Assume we are searching for the needle $d$ with shared prefix pair $(i,j)$ in a tree with root $v$ with key $z$ and shared prefix pair $(p,q)$.
Since the search proceeds from parent to child, the prefix pairs share the same context and the same left and right neighbors, $a$ and $b$.
Now, if $i < p$, then $z[i] = a[i] < d[i]$, and $z < d$.
In this case, the search proceeds recursively to the right child of $v$.
$z$ is the new left neighbor of $d$ and $d$'s prefix pair stays the same.
If $i > p$, then $d[p] = a[p] < z[p]$, and $d < z$.
In this case, the search proceeds recursively to the left child of $v$.
$z$ is $d$'s new right neighbor and $p$ is the new right shared prefix of $d$.
For $j \neq q$, proceed similarly.
In the remaining case, $i = p$ and $j = q$.
Assume w.l.o.g., that $i \geq j$.
Find the first $i^{\prime} > i$ such that $d[i^{\prime}] \neq z[i^{\prime}]$ but $\forall n < i^{\prime}, d[n] = z[n]$.
If $d[i^{\prime}] < z[i^{\prime}]$, then $d < z$, so proceed to the left child of $v$.
The new right neighbor of $d$ is $z$ and the new right shared prefix of $d$ is $i^{\prime}$.
If $d[i^{\prime}] > z[i^{\prime}]$, then $d > z$, so proceed to the right; $z$ is the new left neighbor of $d$, and $i^{\prime}$ is $d$'s new left shared prefix.
The $j > i$ case is symmetric.
Search Performance
Letters are not compared unless $i=p$ and $j=q$.
At each step in which letters are compared, either the sum of the shared prefix pair increases or only one letter comparison is made.
We will discuss these two separately.
If only one letter comparison is made, a child pointer is immediately followed.
Since paths from the root to leaves are $O(\lg n)$ and $n \leq A^k$, fewer than $O(k \lg A)$ single-letter-comparison steps are taken.
If $p > 1$ letter comparisons are made in a step, the sum $i+j$ of the shared prefix pair increases by at least $p-1$.
Since the maximum possible sum is $2k$, $O(k)$ letter comparisons are made in comparisons that result in larger shared prefix pair sums.
However, shared prefix pair sums may seemingly decrease in non-letter-comparison steps when $i > p$ and $j$ is replaced by $p$ or $j > q$ and $i$ is replaced by $q$.
This is not the case, though:
If $i > p$ then $d < z$, so $j \leq q$.
If $j < q$, then $d$'s new right shared prefix is $j$, so $j = p$ and the shared prefix pair sum is not decreased.
Similarly, if $j = q$, then $d$'s new right shared prefix is $\geq j$, and the sum is not decreased.
Similarly, each step requires $O(1+p/B)$ block transfers if it makes $p-1$ letter comparisons.
Insertion and Deletion
To perform an insertion, first locate where the node with the key $d$ would be found if it were in the tree.
After modification, perform the necessary $O(\log n)$ restructuring necessary to restore balance.
Rotations might invalidate shared prefix pairs.
Consider the case of a left rotation:
B
/ \
A D
/ \
C E
D
/ \
B E
/ \
A C
The shared prefix pairs at A, C, and E all remain valid.
The left shared prefix of B and the right shared prefix of D also remain valid.
The right shared prefix at B is the left shared prefix at D from before the rotation.
The left shared prefix of D is the minimum of the left shared prefixes of D and B from before the rotation.
The right rotation and deletion cases are the same, mutatis mutandis.
