$C_u(\mathbb R)^*$ is essentially the space of complex measures on $\beta \mathbb Z\coprod (\beta\mathbb Z\times(0,1)).$ Here $\beta \mathbb Z$ is the Stone-Čech compactification of $\mathbb Z,$ and the $\coprod$ denotes disjoint union.
One can identify $C_u(\mathbb R)$ with $C_0(\beta \mathbb Z \coprod (\beta \mathbb Z\times (0,1)))$ in the following way: for $f\in C_u(\mathbb R),$ and write $f=g+h$, where $g(n)=0$ for all $n\in \mathbb Z$ and $h$ is continuous and linear on each interval $[n,n+1].$ We will identify $g$ with a function $\tilde g:\beta \mathbb Z\times [0,1]\to \mathbb C$ in the following way: since $f:\mathbb R\to \mathbb C$ is uniformly continuous, the functions $g|_{[n,n+1]}, n\in \mathbb Z$ form an equicontinuous family, considered as functions $g_n\in C([0,1]).$ By Arzelà-Ascoli, the set $\{g_n:n\in \mathbb Z\}$ is precompact in the uniform topology. By the universal property of $\beta \mathbb Z$, there is a unique continuous function $\varphi: \beta \mathbb Z\to C([0,1])$ such that $\varphi(n)=g_n$ for $n\in \mathbb Z.$ Now the function $\tilde g(x,y):=\varphi(x)(y)$ is a continuous function from $\beta \mathbb Z\times [0,1]$ to $\mathbb C$; the joint continuity is obtained by again applying equicontinuity of the family $\{\varphi(x):x\in \beta\mathbb Z\}.$
We have identified $f$ with a pair $(\tilde g, h),$ where $\tilde g: \beta \mathbb Z\times [0,1]\to \mathbb C$, $\tilde g(x,0)=\tilde g(x,1)=0$ for all $x\in \beta \mathbb Z,$ and $h:\mathbb R\to \mathbb Z$ is determined by the sequence of values $h(n),n\in \mathbb Z.$ It's easy to check that every such pair $(\tilde g, h)$ uniquely determines a function $f\in C_u(\mathbb R)$ by $f(n+x)=\tilde g(n,x)+h(n+x), x\in [0,1), n\in \mathbb Z.$
If we use the norm $|(\tilde g, h)|:=|\tilde g|+|h|$ (these are sup norms), the identification $f\leftrightarrow (\tilde g,h)$ is an identification of $C_u(\mathbb R)$ with $C_0(\beta \mathbb Z \coprod (\beta \mathbb Z\times (0,1))),$ as Banach spaces.
So it appears that finding a non-obvious element of $C_u(\mathbb R)^*$ is more or less equivalent to finding a non-obvious element of $C_b(\mathbb Z)^*,$ as Greg predicted.
Does
$$\|f\|:=\inf \left\{ \int_0^1 g(x) dx : |f|\le g \text{ everywhere}, g \text{ a step function} \right\}
$$
work?
Then $\|\cdot\|$ is a norm on step functions, Cauchy sequences for $\|\cdot\|$ are Cauchy for $L^1$, and using completeness of $L^1$, pointwise convergence for subsequences of $L^1$ convergent functions, and something like Egorov's theorem, the Riemann integrability of the $L^1$ limit should follow. But I haven't worked out all details :)
Best Answer
Let $(X,\mathcal M)$ be a measurable space and let $\lambda$ be a complex measure on $(X,\mathcal M)$. The total variation $\vert \lambda\vert$ is a positive measure on $(X,\mathcal M)$ with a finite total variation, i.e. such that $\vert \lambda\vert(X)<+\infty$. We define $$ \vert \lambda\vert(X)=\sup_{\substack{{\text{$E_k$ pairwise disjoint}}\\{\text{with union $E$, $E_k\in \mathcal M$}}} }\sum_{k\in \mathbb N}\vert\lambda(E_k)\vert. $$ The mapping $\lambda\mapsto\vert \lambda\vert(X)$ is a norm on the vector space $\mathscr M(X,\mathcal M)$ of complex measures on $(X,\mathcal M)$ and make it a Banach space. So what you call the space of bounded measures is $\mathscr M(X,\mathcal M)$. A fact should be noted: a positive measure $\mu$ on $(X,\mathcal M)$ is not always a complex measure in particular since $\mu(X)$ may be $+\infty$.
Regarding your question, you may require a somewhat stronger property which would be $$ \hat \mu\hat f\in L^1(\mathbb R).\tag{$\sharp$} $$ This implies $\mu\ast f\in L^\infty$ with a norm smaller than the $L^1$ norm of $\hat \mu\hat f$. However, you have to make sure that the Fourier transform of $f$ makes sense as well as the product. For instance when $f(x)=e^{-\vert x\vert}$, this would require $$ \hat\mu(\xi)=(1+\xi^2) g(\xi),\quad\text{with $g\in L^1(\mathbb R)$,} $$ providing examples. A weaker requirement than $(\sharp)$ would be $$ \hat \mu\hat f\text{ is a bounded measure}.\tag{$\flat$} $$ As noted in my comment below that would contain the case $f=e^{-\vert x\vert}$ and $\mu$ the Dirac comb.