If we make two simplifying assumptions---first, that the times are integers in 24 hour format and second, that no row spans into the next day---then the following may work.
randTime <- function(DF) {
# Double each value. This way, we can sample integers and then divide by two
# to get "on the half-hour" values.
newDF <- DF * 2
# Next, figure out how many possible half hours choices there are. That should
# be equal to EndTime - StartTime - 4 where the last 4 is for the hour buffer
# on either side. Store this in a vector
validTimes <- newDF$EndTime - newDF$StartTime - 4
# Now pick a random number from 1 to validTimes for each entry
randHalf <- vapply(validTimes, sample, integer(1L), size = 1L)
(randHalf + newDF$StartTime) / 2
}
Using your initial data set, we get:
DF <- data.frame(StartTime = c(8, 8, 8, 14, 12),
EndTime = c(14, 12, 16, 18, 18))
> DF
StartTime EndTime
1 8 14
2 8 12
3 8 16
4 14 18
5 12 18
set.seed(278L)
> randTime(DF)
[1] 9.0 8.5 10.5 15.0 13.5
> randTime(DF)
[1] 8.5 8.5 12.5 16.0 14.0
Extra steps to format the output as times or convert the input from characters should not be too difficult.