Elliptic Curves and Small Message Space Let $G$ be the generator of an elliptic curve $E$ of order $n$. Let $M$ denote a small (say, size $2^8$) message space. Elements of $M$ are mapped to points in $E$; the mapping is considered public. Let $s$ be a randomly choosen (secret) number from $[1,n-1]$. For some $m\in M$, is it computationally tractable to recover $m$ from an encoding of the form $sG+m$?
Define $\mathbb{G} = \langle G \rangle$ the cyclic group generated by $G$.  The order of $\mathbb{G}$ is $n$.

In your scheme, an 8-bit message is encoded as a point $m = kG$.  An attacker gets access to the value of $sG + m$ for a random $s \in [0,n-1]$.  The question is: can the attacker recover the value of $m$ (and then the value of the corresponding message)?  

The answer is no.  To see it, observe that the point $S = sG$ is a uniformly random element in $\mathbb{G}$.  As a result, the point $S + m$ is in turn a uniformly random element in $\mathbb{G}$.