正確さを求めるとかなり込み入った内容になりますが、参考まで。
生成する時刻についての注意
もっとも簡単にランダムな時刻を生成する方法としてはRAND関数を使い、表示形式を時刻形式にするというものが考えられます（下記画像）。
しかしさらに表示形式を変えてミリ秒まで表示させるとこうなります。
秒だけでなくミリ秒まで端数が生じていることがわかります（実際はさらにミリ秒未満の細かい端数が発生しています）。視覚的に時刻に見えるものが欲しいというのであればこれでも問題ありませんが、比較・計算に用いる時刻を生成するなら、なるべく直接入力した時刻と一致するような値を生成する必要があります。
また、時刻を足し算すると（直接入力した時刻との）誤差が発生し得るという点にも注意が必要です。
例として「23:00:00」と「0:00:02」を足したものと、直接「23:00:02」と入力した値は正確には一致しません（=で比較するとFALSEになります）。そこでどのような式で生成するにしても最終的に値を丸めるか、TIME関数のような時刻を生成する関数で出力することが必要になります。
これらを踏まえたうえで、以下ではTIME関数を使い、次の3つを満たす時刻を生成するものとします。
- 指定された2つの時刻の範囲内に収まること
- 直接入力した時刻と値が正確に一致すること
- 候補となる時刻がいずれも等確率で生成されること
「時：分」の時刻を生成する
次の画像ではB3,C3セルに条件となる時刻の範囲が入力されています。
これに対しE3セルに次のような式を入力することで、範囲内に収まる時刻（時と分）を生成しています。
E3セル
=TIME(0,RANDBETWEEN(TEXT(B3,"[m]"),TEXT(C3,"[m]")),0)
「TEXT(B3,"[m]")」はB3セル（最小値）の時刻を「分」に変換した数値（12:00→720）となります。
「TEXT(C3,"[m]")」はB3セル（最大値）の時刻を「分」に変換した数値（14:15→855）となります。
この2つの値をRANDEBETWEEN関数の引数とすることで720から855までのランダムな整数を取得し、それをTIME関数の第2引数（分）とすることで時刻を求めています。
自動的にAM/PMを含む表示形式になるので「h:mm」形式を変えると次のようになります。
（以降の画像でも基本的に「h:mm」か「h:mm:ss」の形式で表示させています。）
さらにミリ秒まで表示させた様子です。1分未満の端数が生じていないことがわかります。
「時：分：秒」の時刻を生成する
ここでもB3,C3セルに条件となる時刻の範囲が入力されています。秒単位で範囲が指定されているのが上記例との違いです。
これに対しE3セルに次のような式を入力することで、範囲内の時刻（時：分：秒）を生成しています。
E3セル
=LET(x,RANDBETWEEN(TEXT(B3,"[s]"),TEXT(C3,"[s]")), TIME(0,QUOTIENT(x,60),MOD(x,60)) )
TIME関数は32767までの値しか受け取れないので、上記の例（時：分）と同じようにTIME関数の第3引数を指定しようとするとエラーになる恐れがあります。
そこでLET関数を使い「ランダムに生成した秒数」をいったんxと名付け、それを60で割った商（整数部分）と余りをそれぞれTIME関数の第2、第3引数として渡し、時刻を生成しています。
ただしTIME関数は小数部分を無視するのでQUOTIENTの部分は「x/60」でも同じ結果になります。
指定範囲を「0:00:00～23:59:59」に拡大してもエラーになりません。
n分（秒）間隔の値を生成する
次の画像では、最小値と最大値のほかに「間隔」となる分数（5）が指定されており、F3セルでこれに沿った時刻を生成しています。
生成される時刻は「最小値、最小値+5分、最小値+10分…」のいずれかとなります（「分」の部分をE3セルの値の倍数に丸めるというわけではないので注意）。
F3セル
=TIME(0,TEXT(B3,"[m]")+FLOOR(RANDBETWEEN(0,TEXT(C3,"[m]")-TEXT(B3,"[m]")+(D3-1)),D3),0)
B3セルの値を「分」に変換した値（720）に、0～135（855-720つまり12:30から14:15までの分数）の範囲で生成した値を加算し、最後にTIME関数で時刻に変換するという内容です。ただし加算する値についてはFLOOR関数を使い5（D3セルの値）分単位に丸めています。
また「+(D3-1)」の部分ですが、最大値（に最も近い値）が生成される確率を補正するためのものです。これがないと（丸めの関係で）最大値が生成される確率が他の時刻より低くなります。
次の画像は同様に「間隔」となる秒数（15）が指定されている例です。
生成される時刻は「最小値、最小値+15秒、最小値+30秒…」のいずれかとなります。
F3セル
=LET(x,FLOOR(RANDBETWEEN(0,TEXT(C3,"[s]")-TEXT(B3,"[s]"))+(D3-1),D3), TIME(0,TEXT(B3,"[m]")+QUOTIENT(x,60),SECOND(B3)+MOD(x,60)) )
これまでの内容をすべてひっくるめたような式です。
TIME関数の引数が32767を超えないよう、B3セルの値を分と秒に分割し、加算するランダムな秒数も分数と秒数に分け、最後にTIME関数でくっつけるという内容です。
ここでも「+(D3-1)」の部分がないと最大値（に最も近い値）の出現率が低くなります。
備考
TIME関数を使う方法にこだわったため、所定の条件を満たすことは確認しやすいものの、かなり面倒な式となりました。
ほかには「TEXT(最小値+(最大値-最小値)*RAND(),"h:mm")」のようにTEXT関数を使って乱数を丸めるアプローチも考えられますが、分単位で丸める時と秒単位で丸める時の値の丸め方が異なる（分単位…1分未満切り捨て、秒単位…1秒未満四捨五入）ため等確率での抽出を行うにあたり考慮する必要がある、というのが注意点です。
