What is the least value of $k$ for which $B^k = I$?

Let's tackle the more general problem with $A^n=I$. We have $$ B^2=A^{-1}BA $$ Therefore $$ A^{-2}BA^2=A^{-1}(A^{-1}BA)A=A^{-1}B^2A=(A^{-1}BA)^2=B^4=B^{2^2} $$ By easy induction, $$ A^{-m}BA^m=B^{2^m} $$ for every integer $m\ge0$, so, in particular, $$ B=A^{-n}BA^n=B^{2^n} $$ and so $B^{2^n-1}=I$.

So certainly $B^{63}=I$.

Note that if $A^2=I$, one would conclude that $B^3=I$. Moreover $B^2=I$ would imply $A=BA$, so $B=I$, which is disallowed. Hence the minimum value for which $B^k$ can be the identity is $3$, certainly not $127$.

Is it possible to find two matrices with these properties? Yes.

Let's work on $3\times 3$ matrices. Consider as $A$ the permutation matrix exchanging rows $1$ and $2$, whereas $B$ is the permutation matrix that sends row $1$ to row $2$, row $2$ to row $3$ and row $3$ to row $1$. Then it's easy to check that $A^{-1}BA=B^2$ and $A^2=I$.

If we remove the hypothesis $A^6=I_n$...

Proposition. Let $B\in GL_n(\mathbb{C})$ s.t. $B^2$ and $B$ are similar. Then, there is a positive integer $k$ s.t. $B^k=I_n+N$ where $N$ is nilpotent.

Proof. Let $\sigma(B)$ be the spectrum of $B$ and $\lambda\in \sigma(B)$. Then $\lambda^2,\lambda^{2^2},\cdots\in\sigma(B)$; it is not difficult to deduce that there is $p\leq n$ s.t. $\lambda^{2^p-1}=1$. Let $k=lcm(2-1,2^2-1,\cdots,2^n-1)$. Then, for every $\lambda\in\sigma(B)$, $\lambda^k=1$ and we are done.

Example. If $n=4$, then $k=lcm(1,3,7,15)=105$.

Remark 1. Of course, if $B$ is diagonalizable, then $B^k=I_n$.

EDIT. Remark 2. We assume $A^6=I$ and we search a couple s.t. the order of $B$ is $63$ (maximal). According to the proof above, necessarily, $n\geq 6$ and, in fact, $6$ is convenient. Indeed, let $a=exp(2i\pi/63)$ and take

$B=diag(a,a^2,a^4,a^8,a^{16},a^{32}),A=[a_{i,j}]$ where $A$ is the permutation defined by: the $a_{i,j}$ are $0$ except $a_{i,i+1}=1,a_{n,1}=1$. Then $A^6=I,ABA^{-1}=B^2$.