Let's start with defining what Mastery is NOT
Mastery does not Guarantee Perfection:
A master stone napper can usually craft an arrow head to within 1-3 millimeters of an intended shape, but lacks the sensory and motor control faculties to shape it with machine level precision. A master still makes mistakes, but very much more rarely. Also, a master is still limited by his materials; so, if you want to make a bow, a master can make a one to the exact dimensions he intends, but can not necessarily know if the wood will split or hinge due to an unforeseen defect in the wood. A master is still limited by scarcity; so, he may do something sub-par simply because of time or cost constraints, but has a better idea than a novice about what he is trading off.
Mastery does not Guarantee Organization:
Being an expert at using the weapon in your hand does not make you a tactical genius. A well organized phalanx with very little combat experience can easily wreck a disorganized mob of masterful warriors. This also applies too tools. Just because you can make every detail that goes into building the Colosseum does not mean you have the ability to do it yourself or the ability to coordinate with enough other people to do it.
Mastery does not Guarantee Technological Advancement:
While others have speculated that instant mastery would make technology advance faster, I suspect it would actually have the opposite effect. Necessity is the mother of invention; so, the more you can do without inventing new things, the less reason you have to innovate. Let's take the wood lathe as an example. Somewhere in history, someone decided that it was too hard to carve a stick into a uniform pole; so, they invented a machine to help them do it, but if you came out of your mother's womb able to carve a perfect pole, then you would never have nearly as much of a need to invent something to do that for you.
So how would this all effect Paleolithic warfare?
The general factors that determine the effectiveness of an army are their tactics, training, technology, & moral.
Since your warriors have no special mastery of tactics, it means that good leadership will just as important as ever. With no major differences in the skill of warriors, being able to put them in the most opportune positions on the battlefield will be very important when it comes to gaining an upperhand.
To this end training will remain just as much of an X-factor in your world as it is in ours. You may not need spend time to learning how to use your weapons, but you do need to learn to move in formations, follow orders, and you need to condition your body to be strong and endurant enough to wear your opponent down until he can overwhelmed despite his skill level being about the same as yours.
As I mentioned before, technology will not progress any faster, but it may progress differently. Since a masterful warrior can more easily target the gaps in your armor, armor may be less favored. Instead warriors may prefer to just use a shield and weapon which will allow them to match skill to skill without weighing themselves down needlessly. In the stone age, armor was not that common anyway, but this is something to consider. Bows will likely become far more pivotal to warfare since an expert archer is such a dangerous adversary. Since your warriors are so accurate, longer ranged bows will be extra important; so, this is one area where technology will certainly not stagnate. I would expect your warriors to focus especially on range and arrow speed; so, they would probably adopt some kind of compound recurve bow similar to a Mongolian or Hunnic warbow, environment permitting, or a Yew or Osage longbow if the climate is no good for composites.
Moral is also actually going to be an important factor in your warfare because you stated that "If it's possible, they immediately know ... , and if it's impossible, they also know that too." The more an individual soldier understands his odds of success, the more his moral will be impacted by the knowledge. Normally when a battle take place it is because you have two armies of people who engage one another believing they will win and that they will live. But, if you have two armies where each side can make very accurate predictions about their own strengths and vulnerabilities, it could mean that most soldiers will make their own predictions about if a battle is won or lost before it begins. This means that armies could be very easily routed, either fleeing before a battle begins, or very shortly into the fray once the enemy's capabilities become apparent.