To what fractional Sobolev spaces does the step function belong? (Sobolev-Slobodeckij norm of step function)

Guessing

First I would make a quick guess based on the chart of function space. It groups together Sobolev spaces $W^{s,p}$ with the same value of $\frac n p -s$, because these are related by the embedding theorem. While the inclusion provided by this theorem is strict, the sharpness of the theorem still makes "the spaces with equal $\frac n p -s$ are similar" a useful heuristic.

Your function $f$ fails to be in $W^{1,1}$, because its gradient is not an $L^1$ function but rather a vector-valued measure supported on the boundary of $A$. On the other hand, this measure has finite mass (meaning $f\in BV$), which is pretty close to $W^{1,1}$. So, it seems that $s=1$, $p=1$ is at the edge of spaces to which $f$ belongs. From $$\frac{n}{1}-1 = \frac{n}{2} - s$$ we conclude that for $p=2$ (your question), the relevant $s$ is $s=1-\frac n2$.

This agrees with the situation in 1D, and suggests we won't find anything good when $n\ge 2$. Of course, this is just a guess; it may well be wrong.

Estimating

Recall the layercake principle: the integral of a nonnegative function $g$ is equal to $\int_0^\infty |\{g>t\}|\,dt$ where $|\cdot|$ stands for the measure of the set. So, let's consider the inequality $$ \frac{|f(x)-f(y)|}{\|x-y\|^{2s+n}}>t \tag{1} $$ for large values of $t$ (only they are of interest when the measure space has finite measure).

For (1) to hold, exactly one of $x,y$ must be in $A$; also, both must be within distance $\delta \approx t^{-1/( 2s+n)}$ of the boundary of $A$. This constrains $x$ to a set of measure $\approx \delta $. Also, $y$ must lie in a ball of radius $\delta$ around $x$. So,
$$ \left|\left\{ (x,y) : \frac{|f(x)-f(y)}{\|x-y\|^{2s+n}}>t\right\}\right| \approx \delta^2 \approx t^{-(n+1)/(2s+n)} $$ The integral over $t\ge 1$ converges iff $$\frac{ n+1}{2s+n} >1$$ which is equivalent to $s<1/2$.

(In particular, the "guess" wasn't correct after all.)