Rust, 62 bytes

|mut s,m|{let(i,mut a)=(s,1);while 0<a%256{a*=s;s+=m}(s-i)/m};

Try it online!

A closure whose first argument is the first element of the sequence and whose second argument is the step.

Rust, 58 bytes

|s,m|(|mut i,mut a|{while 0<a%256{a*=i;i+=m}(i-s)/m})(s,1)

Try it online!

A closure whose first argument is the first element of the sequence and whose second argument is the step.

Ungolfed with comments

//Initial element, step
|s,m|
  //i is initial value of s, a is accumulator
  (|mut i,mut a| {
    while 0 < a % 256 {   //while a is not divisible by 2^8
      a *= s;             //Multiply a by the current element of the sequence
      s += m              //Get the next element of the sequence by adding the step
    }
    //Subtract the initial value s to only keep increases of m, divide by m to get how many times it was increased
    (i - s) / m
  )
   (s, 1) //Call with i as s and initial value of accumulator as 1