Dear Georges,
this is a very interesting question. I can't quite answer it, but I have some ideas that may be worth sharing.
1
I think that if you want a geometric meaning it would be sensible to restrict the question to finitely generated algebras over an algebraically closed field. After all the usual meaning of geometric is that it holds over the algebraic closure. So, perhaps one could say that if $A$ is a $k$-algebra, then $f\in A$ is geometrically irreducible if $f$ stays irreducible in $\overline A=A\otimes_k \overline k$.
I feel that your line intersecting the circle example is a bit misleading. In that example $x$ is only irreducible because we can't see its decomposition over $\mathbb R$. If you consider a singular curve defined over $\mathbb R$, all of whose singular points are not (individually) visible over $\mathbb R$, one may call that curve non-singular (over $\mathbb R$) but it is definitely not smooth.
Nevertheless, even though at first I thought this would help make some headway into the question, I have not been able to make much of this stronger condition either.
2
It would also be reasonable to assume that $A$ is integrally closed, just so speaking about divisors is safe.
3
Based on Francois's and Karl's comments one could try to look for locally irreducible elements, that is, $f\in A$ such that $f$ remains irreducible after localization at any maximal ideal. Their condition does give something geometric, but interestingly, local irreducibility seems to be a pretty strong condition. For obvious irreducible but not prime elements such as $x$ in an algebra where $xy=zt$ but nothing else non-obvious holds,
localizing at a prime that contains $x,z,t$ but not $y$ exhibits $x$ as a product, so it is not locally irreducible.
4
Another idea is to look for Cartier divisors contained in the divisor defined by $f$. You give an example where this global assumption fails for an irreducible element. In case somebody (like me at first) thinks that this description might work for geometrically irreducible elements, here is an example for that:
Let $A$ be a regular ring (i.e., all of whose localizations are regular local rings, e.g., the coordinate ring of a smooth affine variety) that is not a UFD.
(Here is one way to construct such a ring: Take an arbitrary smooth projective variety $X$ and let $Z\subset X$ be a hyperplane section. Assume that $Z$ does not generate the Picard group of $X$. This can be achieved if for example $\mathrm{Pic}X$ has rank $\geq 2$ or taking a power of a generator. Then $X\setminus Z$ will be a smooth affine variety with a non-trivial Picard group, so its coordinate ring cannot be a UFD.)
Now let $\mathfrak p\subset A$ be a height $1$ prime ideal that is not principal. This exists by the choice of $A$. Finally let $f\in \mathfrak p$ be a non-zero irreducible element. Then $V(f)\supseteq V(\mathfrak p)$ where the latter is a Cartier divisor. By choice $f$ is not a prime element, so there is a product, say $gh$ that it divides but it does not divide either $g$ or $h$. Now if $V(g)$ and $V(h)$ do not share an irreducible component, then it follows that $V(f)$ is not irreducible (as in the case of $f=x$ when $xy=zt$) which implies that $V(\mathfrak p)\subsetneq V(f)$, so $V(f)$ strictly contains a Cartier divisor even though it is irreducible. (I realize that I have not given a complete example for this behaviour, but I think it is plausible that this can happen).
5
Conclusion (?)
Well, as I said at the beginning I can't really answer your question, but perhaps the answer is that there is no good geometric interpretation. There are other reasons that one may use to argue that geometry corresponds more to ideals than to elements.
One could also take the locally irreducible elements as the irreducible elements corresponding to a geometric meaning. I kind of like that solution as many things in geometry are local. If one wanted to talk about a larger class of elements, one could say that for an $f\in A$, the locus of irreducibility is the subset of $\mathrm{Spec A}$ such that for any point in this locus $f$ is irreducible in the local ring at that point. This should be an open set and then at any point the local irreducibility could be checked by the Francois-Karl criterion.
Remark: The example in the previous point would likely fail to be irreducible somewhere along $V(f)\setminus V(\mathfrak p)$ (not necessarily at the entire set as $f$ would be contained in other height $1$ primes and it seems possible that $V(f)$ is actually the union of Cartier divisors).
Best Answer
Let $n$ be the degree of $f$, so the order is a divisor of $p^n-1$. As the computation of powers in $E$ is a cheap operation, I believe the following could be suitable: If $\alpha^m=1$, then check if there is a prime divisor $r$ of $m$ with $\alpha^{m/r}=1$. If not, then $m$ is the order, and if yes, then set $m=m/r$ and repeat the process.
Start the whole thing with $m=p^n-1$.
Probably there are better ideas, but I cannot think of one.