Search for minimum in an array of $k$ monotonic subarrays
Here are algorithms and matching lower bounds, which fully resolve the situation:


For $k=1$, you can find the minimum in $O(1)$ time: just examine the two endpoints of the array, $A[0]$ and $A[n-1]$.
For $k=2$, you can find the minimum in $O(m + \lg (n/m))$ time, as was mentioned in the question.  I prove below that you can't do any faster than this (up to a constant factor).
For $k\ge 3$, I prove below that finding the minimum takes $\Theta(n)$ time, regardless of $m$ (it takes $\Omega(n)$ time even if you are guaranteed that $m=0$).  The trivial algorithm takes $O(n)$ time, so if $k\ge 3$ it is not possible to do better (up to a constant factor) than the trivial algorithm.


Moreover, randomization doesn't help.



Lower bounds.  For $k=2$, consider an array $A$ that is positive and strictly decreasing on $A[0\ldots r-1]$, then $A[r]=A[r+1]=\cdots=A[r+m-1]=0$, then is positive and strictly increasing on $A[r+m\ldots n-1]$.  Now pick an index $i$ satisfying $r \le i \le r+m-1$, and replace $A[i]$ with $-1$.  Notice that this is an array with $k=2$ monotonic sub-arrays (decreasing-then-increasing).  However, even if you were given the value of $r$, you would still have to examine every element of $A[r\ldots r+m-1]$ to find the minimum, so any algorithm has to take $\Omega(m)$ time.  Moreover, it's easy to show that any algorithm will need $\Omega(\lg n)$ time, so we get a $\Omega(\max(m,\lg n))$ lower bound on the running time.  This implies a $\Omega(m + \lg(n/m))$ lower bound as well.

For $k=3$, consider an array that is positive and strictly increasing on $A[0\ldots n-1]$, then pick an index $i$ and modify $A$ by replacing $A[i]$ with $-1$.  This is an array with $k=3$ monotonic sub-arrays, and to find the minimum, you have to scan every element of $A$, so the running time is $\Omega(n)$.  Notice that in this example, $m=0$, so knowing (an upper bound on) the value of $m$ does not help you speed things up.



If you want a heuristic algorithm for $k=2$ (with no guarantees about worst-case running time), the following randomized algorithm might work well in practice, even though its asymptotic worst-case running time is not any better.

We'll assume the array is decreasing-then-increasing (until you find any evidence to the contrary; if you find evidence that it is decreasing-then-increasing, you can just look at the two endpoints and terminate immediately).  We're going to search for the changeover point (which will be the minimum we're looking for).  To do that, we'll use ternary search with random selection of the two midpoints.

In particular, we'll use random probing to find two indices $i&lt;j$ such that $A[i],A[j]$ are different from each other and from $A[0],A[n-1]$.  Once we have these indices, we can do a case analysis on the relative order of $A[0],A[i],A[j],A[n-1]$ and recurse on either $A[i\ldots n-1]$ or $A[0\ldots j]$.  This is a smaller sub-array of expected size $2n/3$.

How long does it take to find two indices $i,j$ that are acceptable?  We can start by randomly choosing values for $i$ until $A[i]$ is different from $A[0]$ and $A[n-1]$; then we randomly choose values for $j$ until $A[j]$ is different from $A[0],A[i],A[n-1]$.  If there are $m$ repeats, then $n-m$ of the entries are unique; thus, each random choice of $i$ (or $j$) has at least a $(n-m)/n$ probability of finding an acceptable value.  Consequently, the expected number of random probes done is $O(n/(n-m))$.

Also, we recurse on an array whose expected size is a constant fraction smaller, so we expect to do only $\lg n$ recursions.

Of course, the total running time could still be bad (e.g., with the example I gave above), but it might often be OK if you have some reason to think the absolute worst-case inputs are unlikely.