Polyhedrons are a very new data type and it is not unusual that not all possible functions have been overloaded for them.
You can extract the vertex coordinates of a Polyhedron R with R[[1]]; combined with ConvexHullMesh, this allows you to convert the Polyhedron to a MeshRegion and to apply `RandomPoint:
R = RandomPolyhedron[5];
S = ConvexHullMesh[R[[1]]];
RandomPoint[S]
PS.: I have no clue at all what this new datatype is supposed to ship what is not already provided MeshRegions.
N.B: The above answer will work on very limited cases and will fail for the example polyhedron posted above
